[Python] 백준 19598번 - 최소 회의실 개수

1. 문제정보

https://www.acmicpc.net/problem/19598

19598번: 최소 회의실 개수

 

 

2. 풀이

그리디에서 시작 시간과 종료 시작이 주어지는 경우 시작 또는 종료 시간으로 정렬한 후 풀이하는 게 일반적이다. 이 문제의 경우 시작 시간으로 정렬한 후 강의실마다 마지막 수업의 종료시간을 체크하며 정답을 구해나가야 한다.

 

시작해야 하는 강의의 시작 시간이 각 강의실의 마지막 종료시간보다 빠르다면 새로운 강의실을 생성한다. 여기서 포인트는 마지막 종료시간을 비교하는 것인데 heapq로 각 강의실의 마지막 종료시간을 오름차순으로 저장하고 첫 번째 인덱스만 비교한 후 강의가 중첩된다면 새로운 강의실을 생성한다.

 

첫 번째 인덱스만 비교하는 이유는 각 강의실 별로 끝나는 시간을 오름차순으로 정렬했기 때문에 첫 번째 인덱스에서 중첩된다면 나머지 강의실도 중첩될 것이기 때문이다.

 

 

3. 코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    start, end = map(int, input().split())
    arr.append([start, end])

arr.sort()

que = []
heapq.heappush(que, arr[0][1])
for i in range(1, n):
    start, end = arr[i][0], arr[i][1]

    if start < que[0]:
        heapq.heappush(que, end)
    else:
        heapq.heappop(que)
        heapq.heappush(que, end)

print(len(que))