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

문제

• N개의 회의를 모두 진행할 수 있는 최소 회의실 개수 구하기
  • 1 <= N <= 100,000
• 각 회의는 시작 시간과 끝나는 시간이 주어지고, 한 번 시작된 회의는 중단될 수 없다.
• 한 회의실에서는 하나의 회의만 진행 될 수 있다.

 

풀이

• 시간 복잡도
  • N이 최대 10만이므로, $O(N^2)$은 안되고, $O(NlogN)$ 은 괜찮다.
• 우선순위 큐 이용
  • 회의 시간을 정렬한 뒤, 회의가 끝나는 시간을 기록한다.
  • 우선순위 큐에서 가장 빠르게 시작 가능한 회의실을 찾고 이어서 사용 가능한지 확인한다. 
  • 정렬되어 있기 때문에 끝나는 시간만 확인하면 된다.

 

예시 : [[0, 1], [0, 10], [1, 3], [2, 5], [3, 5], [8, 30], [11, 17], [11, 40]]

- (0, 1) : 사용 가능한 회의실이 없으므로 끝나는 시간 1이 추가된다.
	rooms : [1]
- (0, 10) : 사용 가능한 회의실이 있지만, 시작 시간이 더 이르기 때문에 새로운 회의실을 추가한다.
	rooms : [1, 10]
- (1, 3) : 1 시간에 시작 가능하다! => 끝나는 시간으로 업데이트 된다.
	rooms : [3, 10]
- (2, 5) : 시작 시간이 더 이르기 때문에 새로운 회의실 추가
	rooms : [3, 10, 5]
- (3, 5) : 3 시간에 시작 가능하다! => 끝나는 시간으로 업데이트
	rooms : [5, 10, 5]
- (8, 30) : 8 시간에 시작 가능하다! => 끝나는 시간으로 업데이트
	rooms : [5, 10, 30]
- (11, 17) : 11 시간에 시작 가능하다! => 끝나는 시간으로 업데이트
	rooms : [10, 30, 17]
- (11, 40) : 11 시간에 시작 가능하다! => 끝나는 시간으로 업데이트
	rooms : [17, 30, 40]

 

 

import sys
import heapq
input = sys.stdin.readline

N = int(input())
meetings = sorted([ list(map(int, input().split())) for _ in range(N) ])
rooms = []              # 가능한 회의실
for s, e in meetings:
    # 사용 가능한 회의실이 있는 경우
    if rooms and rooms[0] <= s:
        heapq.heappop(rooms)    # 현재 회의시간 제거
    # 회의실 추가하기
    heapq.heappush(rooms, e)

print(len(rooms))

 

References

• 백준 19598번
• 2023.05.03 오늘의 문제