[Python] boj no. 11000 : 강의실 배정

Problem

https://www.acmicpc.net/problem/11000

Idea

문제를 해결하기 위한 아이디어는 다음과 같다.

1. 기본적으로 시작 시간이 빠른 수업의 순으로 강의실을 할당.
2. 현재 진행 중인 수업이 없을 경우 다음 수업 할당.
3. 현재 진행 중인 수업이 있을 경우, 진행 중인 수업 중 가장 빠른 종료 시간을 가진 수업의 종료시간(T_i)과 진행되어야 할 수업의 시작 시간(S_j)을 비교하여
   • T_i > S_j 일 경우, 강의실의 갯수를 하나 추가하고 수업 j에 강의실을 할당.
   • T_i <= S_j 일 경우, 수업 i를 종료시키고 사용중이던 강의실을 수업 J에 할당.

위를 구현하기 위해 각각 시작 시간과 종료 시간을 기준으로 하는 두 힙을 사용했다. 시작 시간을 기준으로 하는 힙을 Schedule, 종료 시간을 기준으로 하는 힙을 Timestamp라고 하면, 우선 모든 수업을 Schedule에 추가한다. 이후 Schedule이 빌 때까지 pop을 하면서 해당 원소를 Timestamp에 푸쉬한다. 이 때, 위의 기준으로 추가될 원소와 Timestamp의 상단 원소와 비교하며 수업의 시작과 종료를 관리했다.

이 때, 현재 사용중인 강의실의 수는 Timestamp의 길이와 같다. 이는 현재까지 필요한 최대 강의실의 수와 현재 사용중인 강의실의 수가 다를 수 있음을 의미한다. .따라서, 현재 timestamp의 길이와 총 강의실의 수가 같을 때만 강의실의 수를 추가하도록 하여 T_i > S_j 인 상황에서 강의실이 필요 이상으로 요구되는 것을 방지했다.

Code

import sys
import heapq

N = int(input())

room = 0

schedule = []
for _ in range(N):
    s, t = map(int, sys.stdin.readline().split())
    heapq.heappush(schedule, (s, t))    # 먼저 시작하는 수업부터 확인할 수 있도록

room = 1
timestamp = []
while schedule:
    s, t = heapq.heappop(schedule)
    if not timestamp:
        heapq.heappush(timestamp, (t, s))   # timestamp가 수업이 끝나는 시간을 기준으로 하도록 파라메터 설정.
    
    else:
        if s < timestamp[0][0] and room == len(timestamp): # t중 최소치보다 추가될 s가 작은 경우, 즉 새로운 교실이 필요한 경우
            room += 1                                      # 현재 사용중인 교실과 추가될 교실의 수가 같으면 교실 하나 추가
        else:
            heapq.heappop(timestamp)                       # t중 최소치보다 추가될 s가 크거나 같은 경우, 즉 수업을 하나 종료시키면 되는 경우
        
        heapq.heappush(timestamp, (t, s))

print(room)

Comment