백준 11000번 강의실 배정 골드5 - Python 풀이

문제를 보자마자 직관적으로 이런 풀이를 떠올릴 수 있는데, 수업 시간표를 <key: 시간, value: 강의 수> 딕셔너리로 생성하고, 각 시간대 중 배정된 강의 수의 최대 값이 필요한 강의실의 개수일 것이다. 

import collections

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

time_table = collections.defaultdict(int)

for s, t in arr:
    for i in range(s, t):
        time_table[i] += 1

print(max(time_table.values()))

그러나 위 풀이는 메모리 초과가 발생한다.

 

어짜피 겹치는 시간대만 확인하면 되므로, 시간대를 정렬해서 계산하면 한번만 순회하여 구할 수 있을 것이다.

배열을 순회하며 강의실이 하나씩 열린다고 상상하면 되겠다. 

이미 개설된 강의실들은 종료 시간만 확인하면 되는데, 그 중에서 가장 종료시간이 빠른 강의실과만 비교하면 된다.

(시작 시간을 기준으로 정렬했기 때문에 어짜피 먼저 시작할 강의들은 이미 강의실에 배정되어있고, 아직 배정되지 않은 강의들은 현재 강의보다 늦게 시작한다.)

1. 강의 시작 전 해당 강의실 강의가 이미 끝나있다면 그 강의실의 종료시간을 갱신하면 되고,

2. 강의가 진행 중이라면 새로 강의실 개설이 필요하다고 판단할 수 있다.

 

따라서 종료시간을 key로 하는 우선순위 큐를 생각할 수 있고, 우선순위 큐의 길이가 강의실의 개수가 된다.

import sys
import heapq

input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
arr.sort()

pq = []
heapq.heappush(pq, arr[0][1])

for i in range(1, n):
    # 시작 시간이 종료 시간보다 뒤(=같은 강의실 가능 =기존 강의실 제거하고 새로 갱신)
    if arr[i][0] >= pq[0]:
        heapq.heappop(pq)
    # 강의실 개설
    heapq.heappush(pq, arr[i][1])

print(len(pq))