[백준] 강의실 배정

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

11000번: 강의실 배정

 

lecture 를 아래와 같이 정렬한다.

 

heapq 를 이용하여 강의(B)가 끝나는 시간을 queue 에 담는다. 만약 강의(B)의 시작 시각이 queue 에 있는 강의(A) 중 가장 빨리 마치는 시간과 비교하여 크면 A 를 queue 에서 빼고 B 를 담는다.

 

이 과정을 반복하여 얻은 queue 의 길이가 최소의 강의실 이용 횟수이다.

 

import sys, heapq

N = int(sys.stdin.readline())
lecture = []
queue = []
answer = 0

for i in range(N):
    lecture.append(list(map(int, sys.stdin.readline().split())))

lecture.sort(key=lambda x : (x[0], x[1]))

for s, t in lecture:
    if queue:
        if queue[0] <= s:
            heapq.heappop(queue)
    
    heapq.heappush(queue, t)

answer = len(queue)

print(answer)