[백준 19598번] 최소 회의실 개수 (python)

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

 

기록

(greedy 6일차) 회의실을 다 돌면서 출발시간과의 차가 가장 최소가 되는 방을 찾도록 이중포문으로 구현했더니 시간초과가 발생했다. 그래서 python heapq 모듈로 항상 min heap 상태의 배열이 되도록 하여 가장 첫번째 회의실만 시간 비교하도록 수정했다. (PriorityQueue는 pop으로만 꺼내볼 수 있기 때문에 heapq 사용했다!)

 

코드

from sys import stdin
import heapq

N = int(stdin.readline())
confs = []
for _ in range(N):
    s, e = map(int, stdin.readline().split())
    confs.append((s, e))
confs.sort(key=lambda x : (x[0],x[1]))

rooms_end = [0]
for start, end in confs:
    if start>=rooms_end[0] : heapq.heappushpop(rooms_end, end)
    else : heapq.heappush(rooms_end, end)
print(len(rooms_end))

먼저 시작시간 오름차순으로 정렬한 회의 배열을 생성한다.

 

각 회의실의 종료시간을 담는 배열[회의실1종료시간, 회의실2종료시간,,]을 만든 후, 가장 빨리 끝나는 회의실과 현재 회의 시작시간을 비교하여 가능하면 해당 종료시간을 갱신하고 아니면 새로운 회의실을 배열에 추가한다. (이 때, 시간초과가 일어나지 않도록 하기 위해 min heap 상태로 유지하여 첫번째 인덱스가 항상 종료시간이 가장 빠른 회의실이 되도록 한다.)