백준 19598 - 최소 회의실 개수 (파이썬)
글 작성자: pental
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)
'Programming > 백준' 카테고리의 다른 글
백준 17944 - 퐁당퐁당 1 (파이썬) (0) | 2025.03.08 |
---|---|
백준 17952 - 과제는 끝나지 않아! (파이썬) (0) | 2025.03.07 |
백준 1300 - K번째 수 (파이썬) (0) | 2025.03.06 |
백준 1303 - 전쟁 - 전투 (파이썬) (0) | 2025.03.06 |
백준 14719 - 빗물 (파이썬) (0) | 2025.03.05 |
댓글
이 글 공유하기
다른 글
-
백준 17944 - 퐁당퐁당 1 (파이썬)
백준 17944 - 퐁당퐁당 1 (파이썬)
2025.03.08 -
백준 17952 - 과제는 끝나지 않아! (파이썬)
백준 17952 - 과제는 끝나지 않아! (파이썬)
2025.03.07 -
백준 1300 - K번째 수 (파이썬)
백준 1300 - K번째 수 (파이썬)
2025.03.06 -
백준 1303 - 전쟁 - 전투 (파이썬)
백준 1303 - 전쟁 - 전투 (파이썬)
2025.03.06