[백준] 11000번 강의실 배정 ★

💡문제접근

• 처음엔 일반적인 최소 강의실 배정의 수를 묻는 줄 알고 정렬한 다음 필요한 강의실의 개수를 세는 방법으로 접근했다가 잘못 이해한 것을 뒤늦게 깨닫고 다시 접근했다.
• 질문게시판에 있는 설명을 참고해서 코드를 작성했다.

💡테스트케이스

입력

3
1 3
2 4
3 5

출력

2

• 문제에 대한 나의 이해가 정확하게 맞는진 모르겠지만 이해한대로 정리하면 다음과 같다.
  A교수가 [1, 3]인 수업을 강의실1에서 진행한다고 하자. 이 때 강의실 1개를 사용하므로 현재까지 사용하는 강의실의 개수는 1개가 된다. 그 다음 [2, 4]인 수업을 강의실2에서 진행한다고 하자. 이렇게 된다면 현재까지 사용하는 강의실의 개수는 2개가 된다. 그 다음 [3, 5]를 생각해보자.
  강의실1에서의 강의 종료 시점이 3이므로 다른 강의실을 사용하지 않고 강의실1에서 [3, 5]인 수업을 진행하면 된다. 따라서 최소 강의실의 개수는 2가 된다.

💡코드(메모리 : 65148KB, 시간 : 400ms)

import heapq
import sys
input = sys.stdin.readline

N = int(input())
timetable = []
for _ in range(N):
    S, T = map(int, input().strip().split())
    timetable.append([S, T])

timetable.sort(key = lambda x : x[0])
heap = []
heapq.heappush(heap, timetable[0][1])   # 첫 번째 강의 종료시간
for i in range(1, N):
    # 강의 종료시간이 다음 강의 시작시간보다 뒤에 있다면?
    if heap[0] > timetable[i][0]:
        heapq.heappush(heap, timetable[i][1])
    # 만약 강의 종료시간이 다음 강의 시작시간과 같거나 앞에 있다면?
    else:
        heapq.heappop(heap)
        heapq.heappush(heap, timetable[i][1])
print(heap)

💡소요시간 : 1h