우선순위 큐

강의실 배정

문제 해석 :"수업이 끝난 직후에 다음 수업을 시작할 수 있다."
->
현재 수업이 끝나지 않은 채 다음 수업이 시작된다면 강의실 한개가 더 필요하다
즉, 이 문제는 현재 수업이 끝나는 시간과 다음 수업이 시작하는 시간이 중요하겠고,
현재 수업 시간이 끝나는 시간보다 다음 수업이 시작하는 시간이 빠르면 강의실 하나를 더 (사용)하고 ,
늦거나 같다면, 현재 수업하는 강의실을 사용하면 된다.(교체)

그래서 우선 순위 큐를 두어 현재 상황에서 가장 먼저 끝나는 강의실을 맨 앞에 두고, 다음 수업의 종료 시간을 힙에 넣어주면 된다. 더 자세한 설명은 코드를 보자

import sys
import heapq
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
	start, end = map(int, input().split())
	lst.append((start, end))
 # 시작 시간이 빠른 순서대로 정렬 (맨 처음 시작하는 강의의 종료 시간이 중요하기 때문이다)
lst.sort(key=lambda x:x[0])
answer = []
# 맨 처음 강의의 종료 시간을 추가
answer.append(lst[0][1])
for i in range(1, n):
	# 현재 강의의 종료 시간이 다음 강의의 시작 시간 보다 느리면 강의실 추가
	if answer[0] > lst[i][0]:
		heapq.heappush(answer, lst[i][1])
	else:
    		# 현재 강의의 종료 시간이 다음 강의의 시작 시간과 같거나 빠르면 현재 강의수업이 끝나고 , 현재 강의실 쓰면 됨 
		heapq.heappop(answer)
		heapq.heappush(answer, lst[i][1])
# 강의실 개수 출력
print(len(answer))