Leetcode 2402. Meeting Rooms III

문제

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [starti, endi] means 
that a meeting will be held during the half-closed time interval [starti, endi). 
All the values of starti are unique.

Meetings are allocated to rooms in the following manner:

Each meeting will take place in the unused room with the lowest number.
If there are no available rooms, 
the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
When a room becomes unused, 
meetings that have an earlier original start time should be given the room.
Return the number of the room that held the most meetings. If there are multiple rooms, 
return the room with the lowest number.

A half-closed interval [a, b) is the interval between a and b including a and not including b.

N개의 방이 주어지고 방들은 각각 0~n-1 의 번호를 가진다.
당신에겐 회의 시간이 담긴 2차원 배열이 주어지는데 배열의 각 원소는 회의의 [시작시간, 끝나는 시간] 을 가지며 회의는
시작시간에 시작해 끝나는 시간을 미포함한 상태로 끝난다.
Ex. [1, 3] -> 1시에 시작해 3시엔 회의가 없어진다.
회의를 할 방은 아래 규칙에 의해 정한다.

1. 남은 방이 있을 경우 가장 번호가 작은 방을 사용한다.
2. 남은 방이 없을경우, 가장 빨리 끝나는 회의 이후에 시작한다, 단 반드시 회의의 길이는 유지되어야 한다.

예약된 회의가 모두 끝났을때, 가장 많은 회의를 한 방의 번호를 리턴하시오,
만약 같은 횟수의 회의를 한 방이 여러개 존재한다면 그중 번호가 가장 작은것을 리턴하시오.

회의가 시작하는 시간은 모든 회의에 대해 겹치는 값을 가지지 않습니다!

예시

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- 0초에 0번 회의실이 사용된다.
- 1초에 1번 회의실이 사용된다.
- 5초에 1번 회의실의 사용이 끝나고 [2, 7] 회의가 1번방에서 시작된다.
- 10초에 0, 1번 회의실의 사용이 끝나고 [3, 4] 회의가 0번방에서 시작된다.
0번 방과 1번 방이 각각 2번 사용되어 그중 작은 번호인 0이 리턴된다.

제한

- 1 <= n <= 100
- 1 <= meetings.length <= 10^5
- meetings[i].length == 2
- 0 <= starti < endi <= 5 * 10^5
- 회의의 시작시간은 겹치지 않는다.

풀이

• 이 문제의 포인트는 회의가 끝나는 시간과 남은 방을 관리하는 각각의 minheap을 만드는 것이다.
• 또한 모든 코드를 실행하기 전에 시작시간의 오름차순으로 모든 회의를 정리하고 회의에 대해 for loop를 돌린다.
• 아래는 for loop 내부를 설명한다.

1. 만약 진행되는 회의가 없다면 방 관리 heap 에서 값을 빼 ( 무조건 0일 것이다. ) 회의가 끝나는 시간을 관리하는 heap에 넣는데
   값은 튜플 형태로 (회의가 끝나는 시간, 사용되는 방) 넣는다.

• 이때 따로 방의 사용 횟수를 나타내는 배열을 미리 만들어두어 방 사용을 카운트 해야 한다.

2. 사용중인 방이 존재한다면 먼저 heap의 값을 확인해 이미 시작한 회의중 끝나는 시간이 지금 시작할 회의 시작시간보다 작거나 같은 경우 전부 빼낸다. 이때 반드시 방 관리 heap에 빼낸 방 번호를 집어넣어 낮은 방 번호가 선택될수 있도록 해야한다.
3. 만약 남은 방의 번호가 담긴 heap이 비어있지 않다면, 그 번호를 사용해 회의를 관리하는 heap에 (회의가 끝나는 시간, 사용되는 방) 으로 넣고 방을 카운트 한다.
4. 만약 남은 방의 번호가 담긴 heap이 비어있다면, 현재로서는 끝나는 회의가 없기에 일단 가장 먼저 끝나는 회의를 pop 해서 회의가 끝나는 시간 + 자신의 회의 길이를 회의가 끝나는 시간으로 정해 3번처럼 진행하면 된다.

코드는 아래와 같다.

from heapq import heappush, heappop

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        
        # 회의 관리용 heap
        heap = []

        meetings.sort(key=lambda k: k[0])

		# 방 사용 횟수 카운팅
        count = [0] * n

		# 남은 방 확인용 heap
        left_room = []

        for i in range(n):
            heappush(left_room, i)

        for start, end in meetings:
        # 회의가 진행중인게 없으면 그냥 0으로 보내는것.
            if len(heap) == 0:
                room = heappop(left_room)
                heappush(heap, (end, room))
                count[room] += 1
            else:
            # 현재 시작시간보다 일찍 혹은 동시에 끝나는 모든 회의를 방에서 빼낸다.
                while len(heap) > 0 and heap[0][0] <= start:
                    heappush(left_room, heappop(heap)[1])
            # 남은 방이 있냐 없냐에 따라 3, 4 번 절차중 하나를 선택한다.
                if len(left_room) > 0:
                    room = heappop(left_room)
                    heappush(heap, (end, room))
                    count[room] += 1
                else:
                    first = heappop(heap)
                    heappush(heap, (first[0] + (end - start), first[1]))
                    count[first[1]] += 1

		# 최댓값을 가지는 최소한의 index를 리턴한다.
        return count.index(max(count))

여담

• Hard치곤 꽤 쉬운듯? 초반에 heap을 생각해 내는데 10분정도 걸리고 바로 풀었따.