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

백준 11000번 강의실 배정

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

문제

풀이

우선 나는 회의실 배정 문제랑 처음에 상당히 유사하게 접근했다. 시간 초과된 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n = int(input())
room = []
for _ in range(n):
    room.append(list(map(int, input().split())))

room.sort(key = lambda x : (x[1], x[0]))


count = 0
visited = [False] * n

while visited != [True] * n:
    count = count + 1
    answer = []

    for i in range(len(room)):
        if not visited[i]:
            if answer == [] or answer[-1] <= room[i][0]:
                visited[i] = True
                answer.append(room[i][1])
    
print(count)

결국 찾아봤더니 heap 을 쓰는 문제였다. heap 을 쓰는 힌트만 가지고 다시 풀어보려고 했는데, heappop 에서 막혀서 결국 틀렸다. 재사용 가능한 강의실을 제거하고, 현재 수업의 종료 시간을 힙에 추가하는 부분이 진짜 어렵더라.

import heapq
import sys
input = sys.stdin.readline

n = int(input())
room = []
for _ in range(n):
    room.append(list(map(int, input().split())))

# 수업을 시작 시간으로 정렬 (종료 시간 기준으로 정렬하는 것은 필요 없으므로)
room.sort(key=lambda x: x[0])

# 최소 힙 (우선순위 큐)
min_heap = []

# 첫 번째 수업의 종료 시간을 힙에 추가
heapq.heappush(min_heap, room[0][1])

for i in range(1, n):
    # 가장 빨리 끝나는 수업이 현재 수업 시작 시간보다 작거나 같다면, 그 강의실을 재사용 가능
    if room[i][0] >= min_heap[0]:
        heapq.heappop(min_heap)  # 재사용 가능한 강의실 제거

    # 현재 수업의 종료 시간을 힙에 추가
    heapq.heappush(min_heap, room[i][1])

# 힙에 남아 있는 원소의 개수가 필요한 강의실의 수
print(len(min_heap))

📌 주의

애증의 힙... 힙... 힙...