[Python] 19598. 최소 회의실 개수

문제

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

19598번: 최소 회의실 개수

 

---

풀이 과정

1931번 회의실 배정 문제가 떠오르는 문제였다. 

처음에는 회의실이 없다면 새로 만들고 회의실마다 시간을 비교해주면서 계산하는 2중 for문을 생각했는데 그렇게 하면 시간 초과가 날 것 같아 고민을 했다. 
가장 먼저 끝나는 곳을 찾고 비교하는 것이 관건이었으므로 최솟값과 최댓값을 빠르게 찾는 heap이 생각나 이를 사용하여 해결할 수 있었다. 
회의 끝나는 시간을 heap에 넣고, heap의 제일 처음 값과 다음 회의의 시작하는 시간과 비교하는 방식으로 문제를 해결할 수 있다. 

풀이 과정은 아래와 같다. 

1. 입력받은 회의 정보들을 정렬해준다. (시간 순으로 비교해야 하므로)
2. 회의실 리스트(meeting_rooms)에 맨 처음 시작하는 회의의 끝나는 시간(meetings[0][1])를 회의실에 넣어준다.
3. 두 번째 회의 정보부터 끝까지 for문을 돌면서 가장 먼저 끝나는 회의와 비교한다.
   3-1. 회의(meeting)가 회의실에서 가장 먼저 끝나는 회의보다 먼저 시작한다면, 회의실이 필요하므로 회의가 끝나는 시간을 회의실 리스트에 넣어준다.
   3-2. 회의실에서 가장 먼저 끝나는 회의보다 늦게 시작한다면, 가장 먼저 끝나는 회의의 끝 시간을 현재 회의의 끝나는 시간으로 대체시킨다. (회의실 추가하지 않고 다른 회의가 끝나면 사용 가능)
4. 따라서 남은 회의실 개수가 최소 회의실 개수가 된다. 

 

* heapreplace

: heap에서 최솟값을 pop 하고, 입력받은 값을 push 하지만 heap 크기는 변경되지 않는다. heappop한 다음 heappush하는 것보다 효율적이다. (하지만, heap이 비어있으면 인덱스 에러가 발생한다.)

* 공식 문서 참고 
https://docs.python.org/ko/3/library/heapq.html

 

---

코드

import heapq
 
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:]:
    # 1. heapreplace 사용 => heappush, heappop 두 연산을 하는 것보다 효율적이다. 
    if meeting[0] < meeting_rooms[0]:
        heapq.heappush(meeting_rooms, meeting[1])
    else:
        heapq.heapreplace(meeting_rooms, meeting[1])
    
    # 2. heappop, heappush 사용
    # if meeting[0] >= meeting_rooms[0]:
    #     heapq.heappop(meeting_rooms)
    # heapq.heappush(meeting_rooms, meeting[1])
 
print(len(meeting_rooms))