[Python/파이썬] 백준 19598번 최소 회의실 개수

https://www.acmicpc.net/problem/19598

 

코드

from heapq import heappop, heappush

n = int(input())
time = []
for _ in range(n):
    s, e = map(int, input().split())
    time.append((s, e))
time.sort()  # 시작 시간을 기준으로 오름차순 정렬

hq = []  # 우선순위 큐 => 사용 중인 회의실들의 사용 종료 시각
for i in range(n):
    if hq and hq[0] <= time[i][0]:  # 지금 사용할 수 있는 회의실이 있다면
        heappop(hq)
    heappush(hq, time[i][1])
print(len(hq))

 

1개의 회의실이 아닌 최소의 회의실을 사용하여 N개의 회의를 모두 진행해야 한다. 그렇기 때문에 매회의마다 지금 당장 사용 가능한 회의실이 있다면 거기로 넣고, 없다면 새로운 회의실을 하나 추가한다고 생각하면 된다.

이렇게 하려면 우선 회의들을 시작 시간을 기준으로 오름차순 정렬해주면 된다. 시작 시간이 빠른 회의부터 스케줄을 잡아주어야 쓸데없이 빈 회의실이 나오지 않게 된다.

이런 경우 종료 시간을 기준으로 정렬하여 스케줄을 잡는다면 (5, 15)가 회의를 끝내고 나온 회의실을 (20, 25)가 가져가게 돼서 3개의 회의실을 쓰게 된다. 그렇기 때문에 시작 시간을 기준으로 오름차순 정렬해야 회의실이 미사용되는 시간을 줄여서 최소의 회의실을 사용할 수 있게 된다.