풀이

강의가 시작하는 순으로 정렬
다음 강의의 시작이 이전 강의의 끝나는 시간보다 빨리 시작하면 다른 강의실로 배정

코드

from heapq import *
import sys
input = sys.stdin.readline
N = int(input())
time_table = []
for _ in range(N):
    start, end = map(int,input().split())
    time_table.append((start, end))
heapify(time_table)
start, end = heappop(time_table)
cls = [(end, start)]
while time_table:
    if time_table[0][0] < cls[0][0]:     
        start, end = heappop(time_table)
        heappush(cls, (end, start))
    else:
        start, end = heappop(time_table)
        heapreplace(cls, (end, start))
print(len(cls))

코드 개선

from heapq import heappush, heapreplace
import sys
input = sys.stdin.readline
N = int(input())
time_table = []
for _ in range(N):
    start, end = map(int,input().split())
    time_table.append((start, end))

time_table.sort()
cls = [(time_table[0][1], time_table[0][0])]
for i in range(1, len(time_table)):
    start, end = time_table[i]
    if start < cls[0][0]:
        heappush(cls, (end, start))
    else:
        heapreplace(cls, (end, start))
print(len(cls))

생각해보니 time_table에 heappush 하지 않으니 굳이 힙을 사용할 필요가 없었다. sort 후 while대신 for문을 사용한 인덱스 순회로 변경
160ms 정도 빨라졌다 :D