백준 19598 - 최소 회의실 개수 (파이썬)

https://www.acmicpc.net/problem/19598

풀이

N = int(input())
courses = []
 
for _ in range(N):
    start, end = map(int, input().split())
    courses.append((start, end))
 
courses.sort()

• N개의 회의 일정이 주어지므로, (시작 시간, 종료 시간) 튜플을 리스트 courses에 저장
• 시작 시간을 기준으로 정렬하여, 빠른 시간에 시작하는 회의를 먼저 처리

from queue import PriorityQueue
 
pq = PriorityQueue()
pq.put(courses[0][1])  # 첫 번째 회의의 종료 시간을 큐에 삽입
count = 1  # 필요한 회의실 개수

• 최소 힙(우선순위 큐)을 사용하여 현재 사용 중인 회의실의 종료 시간을 관리
• 첫 번째 회의의 종료 시간을 삽입하고, 회의실 개수를 1로 설정

for i in range(1, N) :
    earliest = pq.get()
    if earliest <= courses[i][0] :
        pq.put(courses[i][1])
    else :
        count += 1
        pq.put(courses[i][1])
        pq.put(earliest)

• 현재 가장 빨리 끝나는 회의의 종료 시간(earliest)을 확인
• 만약 earliest ≤ 현재 회의의 시작 시간이라면, 기존 회의실을 사용할 수 있으므로 종료 시간만 갱신
• 그렇지 않다면, 기존 회의실을 사용할 수 없으므로 새로운 회의실이 필요하며 count를 증가
• 기존 종료 시간(earliest)도 다시 큐에 넣어서, 유지

코드

# 백준 19598 - 최소 회의실 개수
# 분류 : 그리디 알고리즘
 
from queue import PriorityQueue
 
N = int(input())
courses = []
 
for _ in range(N) :
    start, end = map(int, input().split())
    courses.append((start, end))
 
courses.sort()
 
pq = PriorityQueue()
pq.put(courses[0][1])
count = 1
 
for i in range(1, N) :
    earliest = pq.get()
    if earliest <= courses[i][0] :
        pq.put(courses[i][1])
    else :
        count += 1
        pq.put(courses[i][1])
        pq.put(earliest)
 
print(count)