11000번 강의실 배정

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

---

아이디어

우선순위 큐를 이용하는 문제이다.

1) 강의를 시작 시간, 끝나는 시간으로 오름차순 정렬한다.
2) 강의실을 heap으로 사용할 예정이다.(room_heap)
3) room_heap에 첫번째 강의의 끝나는 시간을 넣어준다.
4) for문은 두번째 강의부터 시작
4-1) 강의를 시작하는 시간이 room_heap의 끝나는 시간보다 크거나 같으면 더 나중에 하거나 끝나자마자 시작하는 것이므로 해당 값은 pop해주고 현재 강의 끝나는 시간을 새로 넣어준다.
4-2) 만약 시작 시간이 끝나는 시간보다 작으면 새로운 강의실이 필요하므로 현재 강의 끝나는 시간을 새로 넣어준다.

+) 힙에 나중에 들어오는 시간이 더 작더라도 heap 내에서 작은 값 먼저 정렬할 것이다.(우선순위 큐) 즉, room_heap[0]은 가장 빨리 끝나는 회의 시간이라는 게 보장된다.

---

코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())
lecture = [list(map(int, input().split())) for _ in range(n)]
lecture.sort(key=lambda x: (x[0], x[1]))

room_heap = [lecture[0][1]] # 끝나는 시간 기록
for i in range(1, n):
    start, end = lecture[i][0], lecture[i][1]
    if room_heap[0] <= start: # 시작시간이 끝나는 시간보다 크거나 같으면
        heapq.heappop(room_heap)
    heapq.heappush(room_heap, end)
print(len(room_heap))