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

문제

n개의 회의. 각 회의는 시작시간, 끝나는 시간
한 회의실에 하나의 회의만 진행
N개의 회의를 모두 진행할 수 있는 최소 회의실 개수 구하기
O(N^2) 안됨. -> 시간 복잡도 고려하면서.

내 코드

import sys
import heapq
sys.stdin = open("input.txt", "rt")

# n개의 회의. 각 회의는 시작시간, 끝나는 시간
# 한 회의실에 하나의 회의만 진행
# N개의 회의를 모두 진행할 수 있는 최소 회의실 개수 구하기
# O(N^2) 안됨. -> 시간 복잡도 고려하면서.

n = int(input())
data = []
for _ in range(n):
    a,b = map(int, input().split())
    data.append((a,b))

data.sort(key = lambda x : (x[0], x[1])) # 시작시간 오름차순

heap = []
heapq.heappush(heap, data[0][1]) # 가장 빨리 끝나는 시간 넣어두고.
cnt = 1
for i in range(1,n):
    start,end = data[i]
    if start < heap[0]: # 진행중인 회의의 끝나는시간보다 현재 회의 시작시간이 작으면
        cnt += 1
    else: # 시작시간이 같거나 크면. 이어서 가능 -> 꺼내기
        heapq.heappop(heap)
    heapq.heappush(heap, end) # 끝나는 시간 넣어.

print(cnt)

코멘트

처음에는 회의 종료시간을 기준으로 우선순위 큐에 넣었다. 근데 반례가 존재한다는 것을 이후에 알게 되었다.

현재 배정된 회의실 중 종료시간은 30, 40
남은 회의는 50-60 / 30-70
50-60 회의가 종료시간 30 회의실 배정
30-70 회의실은 종료시간 40 회의실 배정이 불가하므로 회의실 +1
30-70 회의가 30 회의실을 먼저 배정받고, 50-60 회의가 40 회의실을 배정받으면 추가로 회의실 배정 필요없음

시작시간이 빠른 순 / 시작시간이 같을 경우 종료시간 빠른 순으로 회의를 정렬하면 빨리 시작해야 하는 회의가 최대한 종료시간이 빠른 회의실을 먼저 배정받을 수 있겠다라고 생각했다.