[python/파이썬] 백준 19598 최소 회의실 개수

문제

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

입력

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

출력

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

예제 입력 1 복사

3
0 40
15 30
5 10

예제 출력 1 복사

2

2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의를 진행할 수 없고 3개 이상의 회의실로 3개 회의를 모두 진행할 수 있지만 최소 회의실 개수를 구해야 하기 때문에 2가 정답이 된다.

예제 입력 2 복사

2
10 20
5 10

예제 출력 2 복사

1

 

[문제 풀이]

 

디폴트로 최소 힙을 지원하는 모듈인 heapq를 이용한 문제이다.

강의 시작 시간이 빠른 순서대로 강의들을 정렬한 후에 hq에 강의 종료 시간을 저장하는 방식으로 진행 된다.

 

첫 번째 예제처럼 3개의 강의가 있다고 할 때

시작 시간을 기준으로 정렬하면 아래와 같이 정렬된다.

[ [0,40], [5,10], [15,30] ]

 

기본으로 힙에 0이 들어있기에 어떤 강의라도 시작 시간이 0보다 크거나 같다.

따라서 가장 빠르게 시작하는 강의부터 강의실 배정이 시작된다.

 

heap : 0 

 

0 == 0

heap : 40

 

5 < 40

heap : 10 40

count ++

 

15 > 10

heap : 30 40

 

이러한 흐름으로 진행되어 count값은 2가 된다 -> 강의실 2개 필요!

 

[소스 코드]

import sys
import heapq as hq

input = sys.stdin.readline
n = int(input())

times = [] #시작시간과 종료시간을 저장

for _ in range(n):
    times.append(list(map(int, input().split()))) #리스트 형태로 times에 저장 -> 2차원 배열

times.sort(key=lambda x:x[0]) #시작시간을 기준으로 정렬

arr = [0] #우선순위 큐를 사용하기 위해 가장 작은 값인 0을 기본으로 저장
count = 1 #강의실 개수, 기본적으로 1개부터 시작

for start, end in times:
    if start >= arr[0]: #hq에서 가장 작은 값 : arr[0] 
        hq.heappop(arr) #진행 중인 강의 종료시간보다 시작시간이 늦다면 강의 가능
    else:
        count += 1
    hq.heappush(arr, end)

print(count)