문제
K개의 강의에 대해 필요한 최소 강의실 수를 구하고, 각 강의가 배정된 강의실 번호를 출력하라.
입력
첫째 줄에 강의 수 K, 이후 K줄에 강의 번호, 시작 시간, 종료 시간이 주어진다.
출력
첫째 줄에 최소 강의실 수, 이후 K줄에 각 강의의 배정 강의실 번호를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 2 14 2 3 10 3 8 12 | 2 1 2 2 |
풀이
강의를 시작 시간 순으로 정렬한 뒤, 최소 힙으로 가장 빨리 끝나는 강의실을 관리하여 재사용 또는 신규 배정한다.
- 강의를 시작 시간 기준으로 정렬한다
- 첫 강의를 강의실 1에 배정하고 힙에 (종료 시간, 강의실 번호)를 넣는다
- 다음 강의부터 힙에서 가장 빨리 끝나는 강의실을 꺼낸다
- 새 강의의 시작 시간이 해당 강의실의 종료 시간 이상이면 재사용, 아니면 새 강의실을 배정하고 이전 강의실은 다시 힙에 넣는다
- room 배열에 각 강의 번호별 배정 강의실을 기록한다
핵심 아이디어: 최소 힙으로 가장 빨리 끝나는 강의실을 O(log K)에 찾아 재사용 여부를 판단하면 최소 강의실 수가 보장된다.
코드
import sys
import heapq
input = sys.stdin.readline
def greedy(lecture, room):
hq = []
start, end, lecture_num = lecture[0]
cnt = 1
room[lecture_num] = cnt
heapq.heappush(hq, (end, cnt, lecture_num))
for i in range(1, K):
start, end, lecture_num = lecture[i]
min_end, min_room, min_lecture = heapq.heappop(hq)
if start >= min_end:
room[lecture_num] = min_room
heapq.heappush(hq, (end, min_room, lecture_num))
else:
cnt += 1
room[lecture_num] = cnt
heapq.heappush(hq, (end, cnt, lecture_num))
heapq.heappush(hq, (min_end, min_room, min_lecture))
return cnt, room
K = int(input())
lecture = []
room = [0] * (K + 1)
for _ in range(K):
number, start, end = map(int, input().split())
lecture.append((start, end, number))
lecture.sort()
room_cnt, room = greedy(lecture, room)
print(room_cnt)
for i in range(1, K + 1):
print(room[i])복잡도
- 시간: O(K log K)
- 공간: O(K)