今天 (2/18) 的 Daily 是 Hard 題： 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:

  1. Each meeting will take place in the unused room with the lowest number.
  2. 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.
  3. 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的n個會議室。

給你一個二維整數數組meetings，其中表示一場會議將會在半閉時間區間舉辦。所有的值互不相同。meetings[i] = [starti, endi][starti, endi)starti

會議將會以以下方式分配給會議室：

  1. 每場會議都會在未佔用且編號最小的會議室舉行。
  2. 如果沒有可用的會議室，會議將會延期，直到有空閒的會議室。延期會議的持續時間和原會議持續時間相同。
  3. 當會議室處於未佔用狀態時，將會優先提供給原開始時間更早的會議。 返回舉辦最多多次會議的房間編號。如果存在多個房間符合此條件，則傳回編號最小的房間。

半閉區間[a, b)是a和b之間的區間，包括 a但不包括 b。

Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0.

Example 2:

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.

Constraints:

1 <= n <= 100
1 <= meetings.length <= 10^5
meetings[i].length == 2
0 <= starti < endi <= 5 * 10^5
All the values of starti are unique.

分析

雖然題目跟測資的範例都有點長，但耐心閱讀完之後會發現這是一個經典的「排課問題」，而且本題完全不需思考排法，題目已經嚴格規定了，只要照著把題目的要求打出來就好。

題目的安排會議規則，可以整理如下：

  1. 按照會議(原訂)開始的時間，越早開始的優先分配。

    雖然題目並沒有明著這樣說，但推論一下之後會發現這是很顯然的：

    1. 假設(原訂)開始時間比A會議早的所有會議都已安排，即，A會議是目前仍未安排的會議之中(原訂)最早開始的會議
    2. 若在A會議(原訂)開始的時間有空的房間，因為其他剩餘的會議都還未達開始時間，當然優先分配A會議
    3. 若A會議(原訂)開始的時間沒有空的房間，必須延期，則在某間房間空出來時，根據題目的分配規則3，仍優先分配A會議

  2. 持續記錄並更新每間房間「下一次」能安排會議的時間

    亦即，前一次會議的結束時間(若從未安排會議，則紀錄為0)，稱其為availableT

  3. 假設目前要分配的會議，其開始與結束時間分別為startT, endT

    1. 若所有房間中，有1~數間availableT <= startT的房間，則分配至這些房間中房間編號最小的房間
    2. 若所有房間的availableT均> startT，則分配至這些房間中availableT最小(最早空出來的)房間

  4. 無論如期舉行或者延期，所有會議的長度都保持不變

    即：房間的下一次availableT = 會議真正開始的時間 + endT - startT

解題思路

方案一、暴力解

本題不須設計算法，只要逐一拆解上述的安排規則，並將其轉換為程式碼即可：

  1. 越早開始的會議越早分配

    sort：

    將meetings陣列排序即可

  2. 持續記錄並更新每間房間安排到的會議數量

    counting：

    建立一個長度為n的list count並初始化其元素為0，每當第i房間分配到會議便對第i格的值+1即可

  3. 選中應分配的房間

    一個簡單的想法如下：

    1. 建立一個長度為n的list，其值為每間房間的下一次有空時間(availableT)。
    2. 篩選所有的值，找出其中availableT <= startT的值：
      1. 若有，則取其中index最小的房間
      2. 若無，則取所有的值中availableT最小的房間

  4. 更新紀錄的資訊：將應分配的房間的：

    1. cnt +1
    2. availableT修改為：其真正開始時間 + endT-startT

  5. 回傳cnt最大的房間中id最小的

範例程式碼：(Python 3)

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        rooms = [i for i in range(n)]
        meetings.sort()                       
        cnt = [0]*n                           
        availableT = [0]*n                    
        for startT, endT in meetings:
            emptyRooms = list(filter(lambda i: availableT[i]<=startT,rooms))
            nextRoom = min(emptyRooms) if emptyRooms else min(rooms, key=lambda i:availableT[i])
            cnt[nextRoom] += 1
            availableT[nextRoom] = max(availableT[nextRoom], startT) + (endT-startT)
        return max(rooms, key=lambda i:(cnt[i], -i))

複雜度分析：

遍歷一次meetings，並且在每次迴圈中遍歷availableT以取出每個會議應分配的房間。

時間複雜度為 T = O(m x n)，其中m=會議數、n=房間數

空間複雜度為 S = O(m)

本題房間數很少 n<=100，然而在步驟3(選出要分配的房間)時遍歷所有房間的作法，當房間數大時會造成效能瓶頸。

優化的策略是利用 Heap (Priority Queue)來替我們挑出符合條件的房間。

方案二、Greedy + Heap (Priority Queue)

有關 優先佇列(最小堆疊) 的介紹可以參考這篇文章的介紹。

已知透過Heap，可以在O(log L)時間內取出其中最小的元素，不過回顧一下本題的需求：

  1. 對於每間房間的下一次有空時間(availableT)：
  2. 篩選所有的值，找出其中availableT <= startT的值：
    1. 若有，則取其中index最小的房間
    2. 若無，則取所有的值中availableT最小的房間

可以發現需要判斷的參數有兩個：availableT以及房間的index，而且還需要先比較所有的availableT 是否有 <= startT。

如何使用 Heap 完成這個需求呢？以下這個貪心策略，恰好能達成要求：

將方案一的步驟3~4改為以下步驟：

  1. 建立一個 minHeap，裡面放 (availableT, room)的 Tuple。room為房間編號，availableT為其有空時間。初始化時，所有room的availableT均設定為0。

  2. 按照開始時間遍歷meetings。假設目前要安排的會議，其開始與結束時間分別為startT、endT

  3. 從 minHeap 中取出房間 (availableT, room)

    1. 若availableT <= startT，則將其值改為(startT, room)，並再次放回minHeap

      這麼做是因為，若有複數間房間的availableT <= startT，則我們選出房間的依據並非availableT，而是房間的 idroom。Python在對tuple做排序時，若tuple的第0格值相同，便會接著比較第1格的值。

      換言之，將所有availableT <= startT的availableT通通修改為startT之後，便可從 minHeap 之中取出 idroom最小的房間

    2. 若 availableT > startT，則這就是要安排的房間。

      1. 將這間房間的cnt +1
      2. 將房間的有空時間改為(startT + (endT - startT) , room )，重新放回 minHeap

    3. 繼續遍歷meetings，安排下一場會議

範例程式碼 (Python 3)

import heapq
class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()                       
        cnt = [0]*n
        rooms = [(0,i)for i in range(n)] # (availableT, room id)
        i = 0
        while i<len(meetings): 
            startT, endT = meetings[i]
            availableT, room = heappop(rooms)
            if availableT < startT:
                heappush(rooms, (startT, room))
            else:
                cnt[room] += 1
                heappush(rooms, (availableT+endT-startT, room) )
                i += 1
        return max((i for i in range(n)), key=lambda i: (cnt[i], -i))

複雜度分析

時間複雜度為 T = O(m log n)，其中m=會議數、n=房間數

空間複雜度為 S = O(m) (minHeap與cnt的大小)

alt text

結語

本題雖然難度是Hard，卻(Python)只要照著題目的規則撰寫邏輯，即使不使用Heap也能pass，或許在contest時limit設計得的更苛刻也說不定。

本題還有一個隱藏的知識點在於：

假如並不指定安排房間的詳細規則，而僅要求「在最短的時間之內讓所有會議結束」並且同樣指定「有複數房間可安排時，優先安排編號較小的房間」，那麼本題題目指定的規則仍然是能得出最佳解的演算法

其證明也很簡單，如同本文開頭所述，這是一個經典的排課問題，題目本身的規則是貪心策略(對最終結束時間貪心)。

感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！