소스 코드

import sys, heapq
input = sys.stdin.readline

N = int(input().rstrip())
times = [tuple(map(int, input().rstrip().split())) for _ in range(N)]
times.sort(key=lambda x: (x[0], x[1]))
end_of_rooms = [0]

for start, end in times:
    if end_of_rooms[0] <= start:
        heapq.heappop(end_of_rooms)
    
    heapq.heappush(end_of_rooms, end)

print(len(end_of_rooms))

풀이 요약

1. 강의 스케줄을 시작 시간 오름차순으로 정렬한다. (시작 시간이 같으면 종료 시간 오름차순으로 정렬. 그래야 더 일찍 끝나는걸 먼저 고려함으로써 빈 시간을 더 많이 확보 가능)

2. 정렬한 강의 스케줄을 시작 시간이 이른 것부터 순회하면서 배정한다. 배정 작업은 아래와 같다.

   1) 최소 힙의 루트 노드(현재 배정된 강의들 중, 종료 시간이 가장 이른 강의의 종료 시간) 와 현재 순회 단계(배정 전)인 강의의 시작 시간을 비교하여, 같거나 시작 시간이 더 뒤에 있다면, 루트 노드를 종료 시간으로 갖고 있는 강의가 포함된 강의실에 해당 강의를 배정할 수 있는 것이므로 배정한다. 이 때 그 강의실의 가장 늦은 종료 시간이 바뀌었으니, 최소 힙에서 루트 노드를 pop해주고, 새로 배정한 강의의 종료 시간을 힙에 넣어준다.

   2) 만약 위와 반대의 경우라면, 이는 곧 현재 있는 모든 강의실에 배정할 수 없다는 것을 의미하므로, 새로운 강의실을 만들고 거기에 배정한 후, 배정한 수업의 종료 시간을 힙에 넣는다.

3. 모든 강의에 대해 2번 작업을 수행한 후, 힙에 남아 있는 종료 시간들의 개수가 곧 강의실의 개수이다. (힙에는 각 강의실에서 가장 늦은 종료 시간을 가진 강의의 종료 시간들이 들어있는 것이므로)

어려웠던 점, 배운 점

• 처음에 종료 시간 오름차순 정렬 후 이것저것 시도해봤는데 답이 안 보여서 다른 사람 풀이를 참고했다. 시작 시간 오름차순 정렬하는 것과 힙을 활용하는 것을 전혀 생각해내지 못했다.. 이런 강의 배정과 같은 유형의 문제를 여러번 본 것 같은데, 이런 유형의 문제를 많이 풀어서 다양한 아이디어를 접해둘 필요가 있겠다.