題目描述:給定一組會議時間區間,計算需要多少間會議室才能同時舉行所有會議。
解題思路:使用最小堆(min-heap)追蹤各會議室當前會議的結束時間。將區間按開始時間排序。對每個新會議:若堆頂(最早結束的會議室)的結束時間 <= 新會議開始時間,彈出並重用該房間(更新結束時間);否則需要新開一間房間。最終堆的大小就是答案。
時間複雜度: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,掃描所有時間點 — 同複雜度,對多個事件型別更通用。