[BOJ] Q11000 강의실 배정

[BOJ] Q11000 강의실 배정

Question

Language: Python

Difficulty: Gold 5

해당 문제는 class의 갯수가 20만개이며, 시간의 경우의 수가 10⁹이기 때문에 누적합을 통해서는 풀이할 수 없다.

위 문제는 heap를 통해 각 강의 시간의 끝나는 시간을 저장한 상태로, 만일 다음 수업의 시작 시간이 가장 빠르게 끝나는 수업의 시간보다 빠른 경우에는 교실을 추가하고, 이미 끝난 수업이 있는 경우 해당 교실로 수업을 배정하는 식으로 하면, 중간에 가질 수 있는 교실의 최대 개수를 구할 수 있다.

강의가 끝나는 시간이 빠른 순서대로 저장하기 위해 heap를 사용하며, heap의 크기가 교실의 크기가 되며 중간과정에서 가장 긴 heap의 길이가 답이 된다.

Solution

from heapq import heappush, heappop
import sys

def solution():
    classes.sort(key=lambda x: x[0])
    heap=[]

    #첫 경우 삽입
    heappush(heap,classes[0][1])

    heapsize=1
    max_heapsize=1

    for start,end in classes[1:]:
        #만일 끝난 교실이 있는 경우
        if heap[0] <=start:
            heappop(heap)
            heapsize-=1

        #해당 수업 추가
        heappush(heap,end)    
        heapsize+=1    
        max_heapsize=max(max_heapsize,heapsize)
    
    print(max_heapsize)

if __name__ == "__main__":
    N=int(input())
    classes=[list(map(int,input().split())) for _ in range(N)]
    solution()