[백준/Python] 1379번 강의실

문제

설명

회의실 배정에서 좀 더 어려워진 유형의 욕심쟁이 기법 문제이다.

출력으로 모든 강의를 진행하는데 필요한 강의실의 개수와, 각 강의에 배정되는 강의실 번호를 출력하면 된다.

 

우선 모든 강의를 시작하는 시간 순서대로 오름차순으로 정렬한다.

그리고 강의가 끝나는 시간을 기준으로 최소 힙을 만들어 강의를 하나씩 집어 넣는데 아래 규칙을 따른다.

1. 최소 힙 루트 원소의 끝나는 시간이 현재 넣어야 하는 강의의 시작 시간보다 작거나 같다면 루트를 제거하고 현재 강의를 넣는다. (진행 중인 강의가 끝나고 같은 강의실에서 진행할 수 있음)

2. 최소 힙 루트 원소의 끝나는 시간이 현재 넣어야 하는 강의의 시작 시간보다 크다면 그냥 넣는다. (강의가 끝나지 않아 새로운 강의실을 만들어야 한다.)

모든 강의를 넣었을 때, 최소 힙의 크기가 총 필요한 강의실의 수이다.

 

그리고 강의실 번호는 처음 넣는 강의부터 1번씩 번호를 붙히는데, 위에서 1번 규칙에 걸리면 해당 번호를 그대로 이어 받고, 2번 규칙에 걸리면 강의실 번호를 하나 높히고 최소 힙에 삽입한다.

 

코드

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

def main():
    n = int(input().strip())
    # lect 배열은 앞으로 넣어야 할 강의들 - 시작 시간 순으로 오름차순 정렬
    lect = []
    for _ in range(n):
        num, s, e = map(int, input().split())
        lect.append((s, e, num))
    lect.sort()
    
    # room 배열은 배정된 강의실들 최소 힙 (종료 시간)
    room = []
    ans = [0] * (n + 1)
    s, e, num = lect[0]
    
    ln = 1
    heappush(room, (e, s, num, ln))
    for l in lect[1:]:
        s, e, num = l
        if s >= room[0][0]:
            done = heappop(room)
            heappush(room, (e, s, num, done[3]))
            ans[done[2]] = done[3]
        else:
            ln += 1
            heappush(room, (e, s, num, ln))
    
    print(len(room))

    while room:
        _, _, num, ln = heappop(room)
        ans[num] = ln
    
    print(*ans[1:], sep='\n')
    
if __name__ == "__main__":
    main()