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

🤔문제 해결

• 우선순위큐

 

• 회의를 오름차순으로 정렬한다.
• 사용한 회의실의 끝나는 시각을 배열로 만든다. 우선순위큐로 사용할 것
• 회의를 하나씩 꺼내서
  • 가장 빨리 끝나는 회의실과 회의 시작 시간을 비교
  • 회의 시작 시간이 더 빠르면 회의실 추가
  • 회의 시작 시간이 더 늦으면 해당 회의실의 끝나는 시각 업데이트

 

🍞 heapreplace는 가장 작은 요소를 빼고, 추가할 요소를 집어 넣는다. ( pop 후 push 를 합친것 - 더 빠르다고 한다.)

 

💻소스 코드

 import sys
import heapq

input = sys.stdin.readline

N = int(input())
meetings = [list(map(int, input().split())) for _ in range(N)]

meetings.sort()

meeting_rooms = [meetings[0][1]]
for meeting in meetings[1:]:
    if meeting_rooms[0] > meeting[0]:  # 회의실 회의 끝나는 시각이 대기중인 미팅 시각보다 늦으면
        heapq.heappush(meeting_rooms, meeting[1])
    else:
        heapq.heapreplace(meeting_rooms, meeting[1])

print(len(meeting_rooms))

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE