[알고리즘] BOJ 19598 최소 회의실 개수

[BOJ] 19598 최소 회이실 개수 바로가기

📍 문제

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

---

📍 입력

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

---

📍 출력

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

---

📍 풀이

✍ 코드

import heapq
from sys import stdin
conf = [] # 강의, 우선순위큐
count = 1 # 강의실 개수

N = int(stdin.readline())
for _ in range(N):
  conf.append(list(map(int,stdin.readline().split())))
conf.sort() # 오름차순으로 정렬
heap = [conf[0][1]]

for i in range(1,N):
  if heap[0] <= conf[i][0]: # 현재 강의실 중 가장 빨리 끝나는 강의실 <= 현재 수업의 시작 시간
    heapq.heappop(heap) #  현재 강의실 중 가장 빨리 끝나는 강의실 제거
  else: # 현재 강의실 중 가장 빨리 끝나는 강의실 > 현재 수업의 시작 시간
    count+=1 # 강의실 1개 추가
  heapq.heappush(heap,conf[i][1]) # 현재 수업 종료 시간 추가
print(count)