MediumRating 1582

253. Meeting Rooms II

arraytwo-pointersgreedysortingheap-priority-queueprefix-sum

解題說明

Meeting Rooms II

題目描述：給定一組會議時間區間，計算需要多少間會議室才能同時舉行所有會議。

解題思路：使用最小堆（min-heap）追蹤各會議室當前會議的結束時間。將區間按開始時間排序。對每個新會議：若堆頂（最早結束的會議室）的結束時間 <= 新會議開始時間，彈出並重用該房間（更新結束時間）；否則需要新開一間房間。最終堆的大小就是答案。

C++ 解法

複雜度分析

時間複雜度：O(n log n) — 排序加上堆操作各 O(n log n)。

空間複雜度：O(n) — 堆最多存 n 個結束時間。

虛擬碼

1. Sort intervals by start time
2. Create min-heap of end times
3. For each interval:
   a. If heap top <= interval.start: pop (room is free)
   b. Push interval.end into heap
4. Return heap.size()

其他解法

優先隊列（最小堆）O(n log n)：按起時排序，用堆維護房間結束時間 — 等價但邏輯更直觀。

掃描線 + 計數 O(n log n)：為開始/結束事件賦予 +1/-1，掃描所有時間點 — 同複雜度，對多個事件型別更通用。

延伸思考

若會議動態增減？
如何最小化最大房間容納人數？
若房間有不同容納上限？

Meeting Rooms II — CaffeCode