[BOJ-11000] 강의실 배정 (Python)

🤒 문제

BOJ-11000 강의실 배정

💊 풀이

이 문제는 boj-1931 회의실 배정 과 함께 보면 좋다.
회의실 배정은 한 회의실을 가지고 최대한 많은 회의를 하도록 하는 것이고, 강의실 배정은 최소의 강의실을 사용해 모든 수업을 가능하게 하는 것이다.

Si < Ti 이기 때문에, 강의 시작시간이 늦을수록 끝나는 시간도 늦을 것이다.
A(3,5), B(2,4) 라고 했을 때, 늦게 시작하는 강의 A가 강의실에 먼저 배정이 된다면 그 다음 배정되는 강의 B의 끝나는 시간이 A의 시작시간보다 늦기 때문에 같은 강의실에 배정 할 수 없게 된다.

따라서 이 문제에서 최소의 강의실을 사용하려면, 시작시간을 기준으로 오름차순 으로 정렬한 뒤 배정해야 한다. 나는 heapq모듈을 사용해 정렬했다. 문제 푸는 과정은 이렇다.

1. 입력 받은 강의 정보를 courses에 시작하는 시간을 기준으로 최소힙이 되도록 heappush()한다.

2. 시작 시간을 기준으로 오름차순으로 정렬했기 때문에, i번째 다음 i+1번째를 배정할 때, 같은 강의실에서 i+1번째를 i번째보다 더 이른 시간으로 배정할 일은 없다. 따라서 해당 강의실에 가장 늦게 배정된 강의의 끝나는 시간만 알고 있으면, 그 다음 강의를 배정 할 수 있다.

3. 최소힙 end_time에 첫번째 강의의 끝나는 시간을 넣고 시작한다.

4. courses 를 모두 배정할 때까지 while문을 돌며, course를 하나씩 pop한다. (S, T)

5. 끝나는 시간이 가장 빠른 강의실과 pop한 강의의 시작 시간 S를 비교하여 원래있던 강의실에 배정할 수 있다면 원래의 강의실의 end_time을 pop하고 T를 push한다. 배정 할 수 없다면 pop 하지 않고 push 한다. 즉 사용 강의실이 하나 늘어난다.
   (end_time[0] 과만 비교하는 이유는, end_time[0]이 최소힙의 루트, 최솟값이기 때문에 end_time[0] <= S를 만족하지 못한다면 나머지도 만족 못하기 때문.)

6. 강의 배정을 다 끝내고 end_time의 length를 구하면 그것이 답

✨ 소스코드

import sys
import heapq

N = int(input())

courses = []
end_time = []

for _ in range(N):
    S, T = map(int, sys.stdin.readline().split())
    # 시작하는 시간 기준 최소힙
    heapq.heappush(courses, (S, T))

heapq.heappush(end_time, heapq.heappop(courses)[1])

while courses:
    S, T = heapq.heappop(courses)

    if end_time[0] <= S:
        heapq.heappop(end_time)

    heapq.heappush(end_time, T)

print(len(end_time))