[백준][Python] 19598번 최소 회의실 개수

19598번: 최소 회의실 개수

 

코드

import sys
import heapq

n = int(input())
time = []
for _ in range(n):
    s,e = map(int,sys.stdin.readline().split())
    time.append([s,e])
time.sort()
heap = []
cnt = 1
heapq.heappush(heap, time[0][1])
for i in range(1,n):
    if time[i][0] >= heap[0]:
        heapq.heappop(heap)
    else:
        cnt+=1
    heapq.heappush(heap,time[i][1])
print(cnt)

 

설명

먼저 시작 시간과 끝나는 시간을 입력 받아서 시작 시간을 기준으로 오름차순으로 정렬을 한다. 

그다음 우선순위 큐에 우선 가장 일찍 시작하는 회의의 끝나는 시간을 넣어준다.

그리고 순서대로 이 회의가 끝나는 시간과 다음 회의의 시작 시간을 비교해서 만약 시작 시간이 더 느리거나 같을 경우 현재 우선순위 큐에 있는 것을 pop 해주고 끝나는 시간을 업데이트 해준다.

만약 시작 시간이 더 빠를 경우 그 회의와 같은 회의실을 사용할 수 없기 때문에 cnt 값을 1 더해주고 우선순위 큐에 끝  나는 시간을 push 해준다.