문제

N개의 강의가 있다. 각 강의는 시작 시간과 끝나는 시간이 정해져 있다. 최소한의 강의실을 사용하여 모든 강의를 진행하려고 한다.

강의실의 최소 개수와 각 강의가 어느 강의실에서 진행되는지를 구하는 프로그램을 작성하시오.

풀이

그리디 + 우선순위 큐를 사용하는 문제이다. 시작 시간 순으로 정렬하고, 가장 일찍 끝나는 강의실에 배정한다.

코드

import heapq

N = int(input())

lessons = []
for _ in range(N):
    i, s, e = map(int, input().split())
    lessons.append((s, e, i - 1))

lessons.sort()
room_end = [(lessons[0][1], 1)]
result = [0] * N
result[lessons[0][-1]] = 1
room_cnt = 1

for s, e, i in lessons[1:]:
    # 가장 일찍 끝나는 방
    min_end, room_i = heapq.heappop(room_end)
    # 그 방을 사용 가능할 경우
    if min_end <= s:
        heapq.heappush(room_end, (e, room_i))
        result[i] = room_i
    # 사용 못하는 경우 -> 새로운 방
    else:
        # 원래대로 복구
        heapq.heappush(room_end, (min_end, room_i))
        # 새로운 방 만들기
        room_cnt += 1
        result[i] = room_cnt
        heapq.heappush(room_end, (e, room_cnt))

print(room_cnt)
print(*result, sep='\n')

시간 복잡도

O(N log N)