[BOJ] 백준 19598번 문제 풀이 (Python)

1. 풀이

N개의 회의를 모두 진행할 수 있는 최소 회의실 갯수를 구하는 문제이다. $1 \le \text{N} \le 100000$ 이기 때문에 최대 $\text{O(NlogN)}$이내 풀 수 있는 알고리즘이 필요했다.

결과적으로 정렬과 priority queue를 이용하여 $\text{O(NlogN)}$ 이내 풀 수 있는 알고리즘을 구하였다.

1. 주어진 입력을 시작시간 기준으로 오름차순 정렬.
2. priority queue를 초기화.
   • priority queue는 현재 사용되는 회의실의 끝나는 시간을 포함한다.
3. 첫번째 회의부터 priority queue의 첫번째 원소와 비교
   • priority queue 반환값: 현재 사용되는 회의실 중 가장 빨리 끝나는 회의실의 시간을 반환.
   • 만약 현재 회의가 priority queue 반환값보다 작다면 회의실이 1개 더 필요하다.
4. 최종적으로 priority queue의 길이를 출력.

import sys
import heapq

n = int(input())
meetings = [tuple(map(int, input().split())) for _ in range(n)]
meetings.sort(key=lambda x: (x[0],[1]))

q = [meetings[0][1]]
for start, end in meetings[1:]:
    t = heapq.heappop(q)
    if start < t:
        heapq.heappush(q,t)
        heapq.heappush(q,end)
    else:
        heapq.heappush(q,end)
print(len(q))