(백준 알고리즘 문제풀이) 11000번 강의실배정

문제

문제 링크

 

문제 접근

• 강의실은 한정적이기 때문에 최소 강의실 사용한다.
• 강의는 모두 Si ~ Ti까지 강의를 진행한다.
• 수업이 끝난 직후에 다른 수업이 진행 가능하다.
• 강의 시작시간이 낮은 강의부터 오름차순 정렬을 진행한다.
• 강의가 끝나는 시간을 우선순위큐에 푸쉬를 해주면서 정렬된 강의의 시작시간이 진행중인 강의 종료시간보다 느리다면 우선순위 큐를 팝 해준 후 종료시간 푸쉬를 해준다. 그렇지 않으면 종료시간만 푸쉬를 해준다.
• 결론적으로 강의 시간이 곂치게 된다면 두개의 강의가 동시에 들어가기때문에 강의실의 개수는 우선순위 큐의 길이가 된다.

 코드

import sys
import heapq


def main():
    N = int(sys.stdin.readline())
    SiTi = list()

    for _ in range(N):
        S, T = map(int, sys.stdin.readline().split())
        SiTi.append((S, T))
    SiTi.sort()

    room = list()
    heapq.heappush(room, SiTi[0][1])

    for i in range(1, N):
        Si, Ti = SiTi[i]
        if Si < room[0]:
            heapq.heappush(room, Ti)
        else:
            heapq.heappop(room)
            heapq.heappush(room, Ti)
    print(len(room))


main()

 

느낀점

해당 문제를 고민하면서 긴 시간을 사용하기도 했고, 입력이 언제 되었는지와는 상관없이 우선순위가 높은 개체를 먼저 빼내는 우선순위 큐의 개념에 대하여 정확한 정리를 할 수 있는 문제였다.