BOJ 11000: 강의실 배정 [Python 3]

요즘 Sogang ICPC 팀에 들어가서 그룹으로 알고리즘을 공부하고 있는데,

멘토님께서 추천해주신 첫번째 문제이다.

well-known한 문제라고 하셨는데, 생각보다 어렵고, 처음부터 떠올리기 힘들어서 애를 먹었다.

알고리즘은 정말 간단하다.

import heapq
n=int(input())
data=[list(map(int,input().split())) for _ in range(n)]
data.sort()
q=[]
for i in data:
    if q:
        if q[0]<=i[0]:
            heapq.heappop(q)
    heapq.heappush(q,i[1])
print(len(q))

처음에 들어온 데이터들을 sort해서, 만약 뒤에 있는 강의가 해당 강의실에서 진행 가능하면, 전에 있던 강의는 pop을 하고새로 하는 강의를 heapq에 넣는다.

만약 불가능하면, 추가만 하면 된다.