題目描述:給定區間列表 intervals[i] = [li, ri]。若存在另一個區間 [c, d] 使得 c <= li 且 ri <= d,則稱 [li, ri] 被完全覆蓋。刪去所有被覆蓋的區間後,回傳剩餘的區間數量。
解題思路:排序 + 貪心掃描。
intervals 按 start 升序排序;若 start 相同,則按 end 降序排序。這樣保證:對於相同 start 的一組區間,最大的那個排在最前面,後面的必定被它覆蓋。maxEnd 表示目前見過的最大 end 值。遍歷每個區間:
interval[1] <= maxEnd:當前區間被之前某個區間覆蓋,刪除計數加一(或不計入保留數)。maxEnd = interval[1],保留數加一。由於按 start 升序排列,能確保左端點的覆蓋關係;按 end 降序排列確保相同 start 時最大的先被處理,避免錯誤地把大區間判定為被小區間覆蓋。
時間複雜度:O(n log n) — 排序主導,後續的線性掃描為 O(n)。
空間複雜度:O(1) — 排序為原地操作(不計排序內部的遞迴棧),只使用常數個額外變數。
Function removeCoveredIntervals(intervals):
Sort intervals by start ascending; on tie, by end descending
kept = 0
maxEnd = 0
For each interval [l, r] in sorted intervals:
If r > maxEnd:
kept = kept + 1 // 此區間未被覆蓋,保留
maxEnd = r // 更新見過的最大 end
// Else: r <= maxEnd,被覆蓋,忽略
Return kept暴力法 O(n²):對每個區間,逐一與其他所有區間比較,檢查是否被完全覆蓋。邏輯直觀,但時間複雜度過高,n 較大時會超時。
僅按 start 排序 + 維護 maxEnd O(n log n):與主要解法本質相同,但排序條件可以簡化為:對 start 相同的情況,由於 end 降序可在排序 comparator 中一次完成,毋需分開處理。本題關鍵在於 end 的降序確保同 start 的大區間先被 maxEnd 記錄,從而正確過濾後續較小的同 start 區間。
掃描線 O(n log n):將所有區間端點轉為帶標記的事件,用掃描線統計每個點被幾個區間覆蓋。可以推廣解決更複雜的覆蓋計數問題,但對本題而言過於複雜。
[0, n](類似 LeetCode 1326「Jump Game VII」的覆蓋問題)?