題目描述:schedule[i] 是第 i 位員工的工作區間列表(已排序,不相交)。找出所有員工都空閒的時間段(即所有工作區間的「空隙」),不包含最早開始前和最晚結束後的無限區間。
解題思路:
此題本質上是「找所有工作區間合併後的空隙」,等同於 LC 56(Merge Intervals)的延伸:
currEnd 追蹤當前合併區間的終點。掃描時:
next.start > currEnd:存在空隙,加入 [currEnd, next.start] 為空閒時間。currEnd = max(currEnd, next.end)。堆(優先佇列)變體:若每個員工的區間已排好序,可用最小堆(min-heap)以 start 為 key 合併 k 個排序串列,時間 O(n log k),適合串流場景。
注意:題目使用自定義 Interval 類(含 start 和 end 成員),solution_code 中包含此定義。
時間複雜度:O(n log n) — 攤平所有區間為 O(n),排序為 O(n log n),線性掃描為 O(n);其中 n 為所有員工區間的總數。若使用堆合併變體(已排序的 k 個串列),時間為 O(n log k),k 為員工數。
空間複雜度:O(n) — 儲存攤平後的區間列表;排序額外使用 O(log n) 遞迴堆疊空間。
1. Flatten all employee schedules into one list: all[]
2. Sort all[] by start time
3. currEnd = all[0].end
4. For i from 1 to n-1:
a. if all[i].start > currEnd:
result.append(Interval(currEnd, all[i].start)) // free gap
b. currEnd = max(currEnd, all[i].end)
5. Return result最小堆合併 O(n log k):由於每位員工的區間已排好序,可用最小堆(以 start 為 key)做 k-way merge,每次取出最早結束的區間並判斷空隙。時間 O(n log k),適合 k 遠小於 n 的情況(如員工少但每人行程密集)。
差分陣列 O(V):若時間值域 V 已知且不大,可用長度 V 的差分陣列標記每個時刻是否有員工工作,最後線性掃描找空閒段——時間 O(V + n),適合值域小的場景。
事件掃描線法 O(n log n):將每個區間拆成「開始事件 +1」和「結束事件 -1」,排序後用計數器掃描,計數從正數降為 0 的區間即為空閒時間——邏輯清晰,適合推廣至更複雜的掃描線問題。