[BOJ] 19598번 - 최소 회의실 개수

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

입력

• 첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.

출력

• 첫째 줄에 최소 회의실 개수를 출력한다.

 

🚦 문제 유형

• Greedy 알고리즘

 

✏️ Solution

이 문제는 저번에 풀었던 강의실 배정 문제와 동일하다.

문제 속 빨간색으로 표시된 부분에서 풀이방법에 대한 힌트를 얻을 수 있다.

먼저, 최소 회의실을 사용하려면 모든 회의마다 회의실을 잡는게 아니라 한 회의실에 최대한 많은 회의가 가능하도록 만들어야 한다.

그리고 회의가 끝난 직후에 다음 회의을 시작할수 있으므로 회의의 시작시간, 끝나는 시간을 비교해서 회의실을 새로 배정받아야 하는 지를 체크해야 한다.

따라서 1번 회의가 끝난 직후 2번 회의가 시작될 수 있다면 1번이 썼던 회의실을 2번이 쓰면 된다.

 

하지만, 어떤 회의 시작시간을 회의 리스트안의 모든 회의가 끝나는 시간과 비교할 필요는 없다.

만약 다음 회의의 시작시간이 이전 회의의 끝나는 시간보다 이른 상황이 여러 개라면, 그때마다 회의실을 배정해야 하기 때문이다.

이것은 최소의 회의실을 만드는 조건에 모순된다.

이전 회의가 끝나는 시간이 다음 회의가 시작하는 시간보다 이르다면, 바로 회의실을 이어서 쓸 수 있기 때문에

끝나는 시간이 가장 이른 회의실만 확인하면 된다. (그리디 방법)

여기서 바로 우선순위 큐를 사용할 수 있다.

문제 풀이 순서는 다음과 같다.

1. 회의 리스트를 회의 시작이 이른 순서대로 정렬한다.
2. 우선순위 큐를 만들어 첫번째 회의 끝나는 시간을 추가한다.
3. 회의 리스트의 1번째 부터 마지막까지 반복문을 실행한다.
   1. 우선순위 큐 첫번째 원소(=첫번째 회의시간이 끝나는 시간)에 접근한다.
   2. 현재 보는 회의 시작 시간이 우선순위 큐의 첫번째 원소보다 작다면, 현재보는 회의시간의 끝나는 시간을 우선순위 큐에 추가한다.
   3. 그게 아니라면, 우선순위 큐의 첫번째 원소를 큐에서 삭제하고 현재보는 회의 시간의 끝나는 시간을 우선순위 큐에 추가한다.

import sys
import heapq

N = int(sys.stdin.readline())
conf = []	# 회의 리스트
for i in range(0, N):
    conf.append(list(map(int, sys.stdin.readline().strip().split(' '))))

conf.sort()
conf_queue = []	# 우선순위 큐에 담길 회의 끝나는 시간
heapq.heappush(conf_queue, conf[0][1])

for i in range(1, N):
    if conf[i][0] < conf_queue[0]:
        heapq.heappush(conf_queue, conf[i][1])
    else:
        heapq.heappop(conf_queue)
        heapq.heappush(conf_queue, conf[i][1])

print(len(conf_queue))

 

⚙️ Review

이 문제는 저번에 풀었던 강의실 배정 문제와 매우 동일하므로 풀이가 동일하다.

강의실 배정 문제풀이 바로가기