백준 온라인 저지, 자료구조 / 1379번: 강의실2 (파이썬 / , 백준 골드문제)

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실 수 K와, 각 강의마다 강의실을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

출력

첫째 줄에 필요한 최소 강의실 개수 K를 출력한다. 둘째 줄부터 N개의 줄에 걸쳐 각 강의에 배정할 강의실 번호를 순서대로 출력한다. 편의상 강의실 번호는 1, 2, ..., K 로 매긴다.

제한

예제 입력 1

8
6 15 21
7 20 25
1 3 8
3 2 14
8 6 27
2 7 13
4 12 18
5 6 20

예제 출력 1

5
4
3
2
4
1
3
4
5

힌트

접근 방법

- 강의 정보를 강의 시간을 기준으로 정렬한다.
- 강의 정보를 반복문을 통해 하나씩 확인한 뒤, 해당 강의의 종료시간과 강의실 번호를 힙에 넣는다.
- 이때 힙에 저장되어있는 종료 시간 중, 현재 탐색 중인 강의의 시작시간보다 작거나 같은 경우 모두 뺀다.
- 매 탐색마다 힙의 길이만큼의 인덱스에 해당하는 것을 강의실 번호로 매겨 이를 강의실 번호를 기준으로 하는 리스트에 저장한다.
- 또한 각 강의실 중 비어있는 위치는 강의실에 대한 minHeap을 통해 구한다.

코드

# https://www.acmicpc.net/problem/1379
# 접근 방법
# 강의 정보를 강의 시간을 기준으로 정렬한다.
# 강의 정보를 반복문을 통해 하나씩 확인한 뒤, 해당 강의의 종료시간과 강의실 번호를 힙에 넣는다. 
# 이때 힙에 저장되어있는 종료 시간 중, 현재 탐색 중인 강의의 시작시간보다 작거나 같은 경우 모두 뺀다.
# 매 탐색마다 힙의 길이만큼의 인덱스에 해당하는 것을 강의실 번호로 매겨 이를 강의실 번호를 기준으로 하는 리스트에 저장한다.
# 또한 각 강의실 중 비어있는 위치는 강의실에 대한 minHeap을 통해 구한다.

import sys, heapq
input = sys.stdin.readline
n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
lecture = [0 for _ in range(n+1)]
arr.sort(key=lambda x: (x[1], x[2]))
room = []
for i in range(1, n+1):
    heapq.heappush(room, i)

minHeap = []
for x in arr:
    while minHeap and minHeap[0][0] <= x[1]:
        end, r = heapq.heappop(minHeap)
        heapq.heappush(room, r)

    r = heapq.heappop(room)
    heapq.heappush(minHeap, [x[2], r])
    lecture[x[0]] = r

print(max(lecture))
for x in lecture[1:]:
    print(x)