Meeting Rooms III 解題教學:3 種解法完整比較|LeetCode 2402 Best Practice

Meeting Rooms III 解題教學示意圖|LeetCode 2402

本文完整拆解 LeetCode 2402 Meeting Rooms III 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Meeting Rooms III 一次弄懂。

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

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.

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 <= 105
  • meetings[i].length == 2
  • 0 <= starti < endi <= 5 * 105
  • All the values of starti are unique.
				
					# time complexity: O(nlogn)
# space complexity: O(n)
from heapq import heappop, heappush
from typing import List


class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        availableRooms = [i for i in range(n)]
        usedRooms = []
        counter = [0] * n

        for startTime, endTime in meetings:
            while usedRooms and usedRooms[0][0] <= startTime:
                ending, room = heappop(usedRooms)
                heappush(availableRooms, room)
            
            if not availableRooms:
                end, room = heappop(usedRooms)
                endTime = end + (endTime - startTime)
                heappush(availableRooms, room)

            room = heappop(availableRooms)
            heappush(usedRooms, (endTime, room))
            counter[room] += 1


        return counter.index(max(counter))




n = 3
meetings = [[1, 20], [2, 10], [3, 5], [4, 9], [6, 8]]
print(Solution().mostBooked(n, meetings))
				
			

Meeting Rooms III 解題思路

這題在 Meeting Rooms II 之上加了兩個限制:房間編號要盡量小,而且房間被佔用時會議要延後而非取消。所以需要兩個堆積——一個放「目前空閒的房號」(最小堆積,確保取到編號最小的),一個放「正在使用中的 (結束時間, 房號)」。延後的會議開始時間要用那間房實際空出的時間重新計算。

Meeting Rooms III 演算法步驟

  1. 把會議依開始時間排序;空閒堆積初始放入 0 到 n-1 的所有房號。
  2. 對每場會議,先把所有結束時間小於等於開始時間的使用中房間釋放回空閒堆積。
  3. 若空閒堆積非空,取出最小房號使用,結束時間為原定 end。
  4. 否則從使用中堆積取出最早結束的房間,把會議延後,結束時間為 該房結束時間 + 會議長度,並累計該房使用次數。

Meeting Rooms III 複雜度分析

項目複雜度
時間複雜度O((n + m) log n)
空間複雜度O(n)

m 是會議數、n 是房間數。排序 O(m log m),每場會議對兩個堆積各做常數次 O(log n) 操作。空間主要是兩個堆積與計數陣列,為 O(n)。

Meeting Rooms III 的邊界情況與常見錯誤

  • 釋放房間時要比較「結束時間小於等於開始時間」,用嚴格小於會少釋放一間。
  • 延後的會議長度必須用原始的 end – start,不能用新的開始時間推算。
  • 使用中堆積的排序鍵要先比結束時間、再比房號,否則編號最小的規則會壞掉。
  • 結束時間可能很大,注意數值型別。

Meeting Rooms III 其他解法比較

解法時間空間說明
每場會議線性掃描所有房間O(m·n)O(n)n 小時可行,n 大就退化
單一堆積加排序後處理O(m log m)O(n)難以同時滿足「房號最小」的規則
雙堆積(空閒 + 使用中)O((n+m) log n)O(n)本文採用