[python] 백준 - 11000(강의실 배정)

골드5 문제이며, 제한 시간은 1초이다.

문제

해결 과정

각 강의의 시작 시간과 끝나는 시간을 이용해서 문제를 풀었다. 우선순위 큐를 사용했는데, 최소 힙(min heap)을 이용했다.

1. 먼저 N개의 수업이 주어지면 시작 시간을 기준으로 정렬해준다.
2. 첫 번째 수업의 종료시간을 heap에 넣어준다. (코드에서는 h라고 명명)
3. 이제 수업들의 시작 시간과 heap의 첫 번째 원소를 비교해서 시작 시간 >= heap의 첫 번째 원소이면 강의실을 재사용할 수 있다는 뜻이며

시작 시간 < heap의 첫 번째 원소라면 강의실을 재사용 할 수 없다는 뜻이다.

따라서 재사용 할 수 있다면 heappop(h)을 해주고 다시 종료 시간을 갱신해주면 된다. 재사용 할 수 없다면 heappop을 하지 않고, 힙에 새로 종료 시간을 heappush() 해주면 된다.

풀이

import sys
import heapq
input = sys.stdin.readline

n = int(input())
time = []
for _ in range(n):
  time.append(tuple(map(int, input().split())))

sorted_time = sorted(time, key = lambda x : x[0])

h = [sorted_time[0][1]]
for lecture in sorted_time[1:]:
  if lecture[0] >= h[0]:
    heapq.heappop(h)
    heapq.heappush(h, lecture[1])
  else:
    heapq.heappush(h, lecture[1])
print(len(h))

 정당성 분석을 해보면 시작 시간을 기준으로 정렬했고, 힙의 첫 번째 원소는 가장 작은 원소라는 것이 보장된다. 따라서 작다면 강의실 재사용이 절대 불가이고 크거나 같다면 반드시 재사용이 가능하므로 이 둘을 비교하는 것은 정당하다.