[백준] [실버1] [그리디] 1931. 회의실 배정

회의실 배정

1931번: 회의실 배정

 

• 내 풀이
  • 각 회의를 입력받을 때마다 그 때까지 가능한 회의의 최대 개수를 구해서 저장
  • 시작 시간이 앞서 저장된 회의 끝시간들 보다 큰 지 비교
  • ⚠️ N(1 ≤ N ≤ 100,000) 이기 때문에 이중 for문 사용하면 시간초과

n=int(input())
cnt=[1]*n
start=[]
end=[]
for i in range(n):
  s,e=map(int,input().split())
  end.append(e)

  for j in range(i):
    if s>end[j]:
      cnt[i]=max(cnt[i],cnt[j]+1)

print(max(cnt))

 

• 다른 사람 풀이
  • 가장 많은 회의시간 구하기 위해서는 종료 시간이 빨라야 한다.
  • 종료시간이 같은 경우 시작시간이 먼저인 것을 먼저 봐야 함
    • ex) (10, 10) 의 회의와 (9,10)회의가 있을 때 (9,10)를 먼저 선택하면, (10,10)의 회의를 선택할 기회가 주어진다.
  • → 따라서 시작시간으로 먼저 정렬을 해준 후에, 종료 시간을 기준으로 정렬
  • 📍.sort(key = lambda x: (a, b)) : b로 정렬 후 a 로 정렬

room.sort(key = lambda x: (x[1], x[0]))

 

 

• 종료시간 순이기 때문에 가능한 회의의 끝시간이랑만 비교해 주면 된다
  • 첫시간이 종료시간보다 큰 경우만 종료시간을 end값으로 설정

n = int(input())
room = []

for i in range(n):
    a, b = map(int, input().split())
    room.append([a, b])

room.sort(key = lambda x: (x[1], x[0]))

cnt = 1
end = room[0][1]
for i in range(1, n):
    if room[i][0] >= end:
        cnt += 1
        end = room[i][1]

print(cnt)

#시작시간으로 정렬 후
room.sort(key = lambda x: x[0])
print(room)
#결과
[[0, 6], [1, 4], [2, 13], [3, 5], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]]

#종료시간으로 정렬
room.sort(key = lambda x: x[1])
print(room)
#결과
[[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]