[Baekjoon 19598] 최소 회의실 개수

문제

💛Ⅴ [Baekjoon 19598 - 최소 회의실 개수]

문제 풀이 방법

이전에 이와 매우 유사한 문제인 [1931-회의실 배정] 문제를 푼 적이 있었다. 테스트를 통과하는데만 집중하고 알고리즘에 대한 회고를 하지 않았기 때문에 이 문제를 풀 때, 다시 처음부터 고민했어야 했다. 앞으로 푸는 알고리즘 문제들은 바로바로 정리하고 이전에 푼 문제들에서도 까다로운 문제들을 조금씩 정리해야 겠다!

이 문제는 그리디 알고리즘 문제이다.
각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
앞에서 풀었던 [1931-회의실 배정] 문제와 조건은 똑같지만, 구하고자 하는 것이 다르다. [1931-회의실 배정]는 최대 사용할 수 있는 회의의 최대 개수를 구해야하기 때문에 회의가 끝나는 시간을 기준으로 정렬하면 되지만, 본 문제는 최소 회의실 개수를 구하는 것이다.
따라서 회의가 끝나는 시간을 기준으로한 우선순위 큐에 시작 순서대로 차례대로 넣으면서, 제일 끝나는 시간이 빠른 회의(우선순위 큐의 0번째 인덱스)와 현재 들어가는 회의의 시작 시간을 비교하여 수행한다.

풀이 코드

Python

import sys
import heapq
input = sys.stdin.readline

N = int(input())
timeList = [list(map(int, input().split())) for _ in range(N)]

timeList.sort(key=lambda x : x[0]) # 시작하는 시간으로 정렬
count = [] # 큐에서 변화하는 방의 개수 저장 -> 최댓값이 답이 된다.
timeTable = []

for new_time in timeList:
    if len(timeTable) == 0:
        heapq.heappush(timeTable, new_time[1])
        count.append(len(timeTable))
    else:
        if timeTable[0] <= new_time[0]: # heap 의 최상위 요소보다 작거나 같다면
            heapq.heappop(timeTable)
            heapq.heappush(timeTable, new_time[1])
        else:
            heapq.heappush(timeTable, new_time[1])
            count.append(len(timeTable))
print(max(count))