[그리드] Python - 11000번, 강의실 배정

import heapq
import sys
input = sys.stdin.readline

N = int(input())
S, T = 0, 1  # define
times = []
for _ in range(N):
    times.append(list(map(int, input().split())))
times.sort(key=lambda x: x[0])

queue = []
heapq.heappush(queue, times[0][T])

for i in range(1, N):
    if times[i][S] >= queue[0]:
        heapq.heappop(queue)
        heapq.heappush(queue, times[i][T])
    else:
        heapq.heappush(queue, times[i][T])

print(len(queue))

직관적으로 대강 설명하자면, 우선 강의 시작 시작이 빠른 순으로 정렬한다.

앞서 queue의 의미부터 언급하고자 하는데, 그것은 '각 강의실들의 마지막 수업이 끝나는 시간'이다.

그 다음 for문을 돌려가면서, 우선순위큐를 이용해 강의의 종료 시간이 가장 빠른 원소를 pop하고, 이것을 times[i]의 시작 시간과 비교한다.

times[i]의 시작 시간과 비교했을 때, 종료 시간이 가장 빠른 것을 가져왔음에도 불구하고 강의를 넣을 수 없다면, 새로운 강의실을 만든다.(else...push)

강의를 넣을 수 있다면, 원래 저장되어 있었던 해당 강의실의 마지막 강의 종료 시간을, 지금 넣을 강의의 종료 시간으로 바꿔준다.(if가 True...pop->push)

마지막으로 queue의 원소가 몇 개 생성되었는지를 출력한다.