435. Non-overlapping Intervals

──────────────────────────────────────────────────────────────────────

435. Non-overlapping Intervals

給一堆時間區間，問最少刪掉幾個，才能讓剩下的區間彼此都不重疊。端點相接（[1,2] 和 [2,3]）不算重疊。

思路

第一步是把問題翻過來講：

最少刪幾個  =  總數 − 最多能留幾個

原題聽起來像是在做「刪除」的決策，翻面之後就變成「最多能排進幾場不衝突的活動」—— 一個標準到不行的問題。刪除很難想，因為刪掉一個會影響後面所有的判斷；保留很好想，因為只要一路往後接就行了。

為什麼不能先合併？ 這題長得很像 56. Merge Intervals，但合併是不可逆的：一旦把重疊的併成一大段，就再也看不出原本是幾個區間、該刪哪一個了。合併會把答案需要的資訊丟掉。

排序之後從早往晚兩兩比較，情況只有三種：

1. 沒有重疊 —— 兩個都留
2. 有重疊，前一個結束比較晚
3. 有重疊，前一個結束比較早

第 1 種不用選，難的是 2 和 3 都必須刪掉其中一個，那該刪哪一個？

刪結束晚的那個

先看第二種情況：

|-------------------|   # previous
    |----|              # current

前一個區間結束得很晚，代表它後面還會跟更多區間打架，所以刪它。反過來如果是第三種情況，前一個結束得早，那就刪掉當前這個。

兩句話合起來就是一句：重疊時，永遠留下結束比較早的那個。

理由是，兩個區間都要跟「後面所有還沒處理的區間」競爭，而它們在這場競爭裡唯一有差別的量就是結束時間 —— 開始時間已經過去了，區間長度也不影響後面。結束得越早，留給後面的空間越大。

為什麼這樣貪不會漏掉答案

用交換論證。假設某個最佳解留的是結束較晚的 X，而我選的是結束較早的 Y（兩者重疊，所以任何合法解都不可能同時留下）。

把最佳解裡的 X 抽掉、換成 Y：因為 Y.end ≤ X.end，原本能接在 X 後面的區間，現在一樣接得到 Y 後面。所以換完之後區間數量不變，仍然是一個最佳解，而且它包含了我的選擇。

既然「包含我這一步選擇」的最佳解一定存在，每一步就可以放心地直接決定，不用回頭。更多這類判斷見 Greedy 模板。

解題方向

寫法一：按開始時間排序

排序後，判斷式的骨架長這樣：

if intervals[prev][1] > intervals[i][0]:      # 有重疊
    if intervals[prev][1] > intervals[i][1]:
        # 前一個結束比較晚 → 刪前一個
        TODO
    else:
        # 前一個結束比較早 → 刪當前這個
        TODO
    count += 1
else:
    # 完全沒有重疊
    TODO

先寫成直觀的版本，把留下來的區間收進一個陣列：

class Solution:            
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()    

        keep = [intervals[0]]
        for i in range(1, len(intervals)):
            last = keep.pop()
            curr = intervals[i]
            if last[1] > curr[0]:
                if last[1] > curr[1]:
                    keep.append(curr)
                else:
                    keep.append(last)
            else:
                keep.append(last)
                keep.append(intervals[i])
        return len(intervals) - len(keep)

但其實不需要真的存下留了哪些，只要知道「上一個保留的區間是誰」。用一個指針 prev 取代整個陣列，空間就從 $O(n)$ 降到 $O(1)$：

class Solution:            
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()    

        prev = 0
        count = 0
        for i in range(1, len(intervals)):
            if intervals[prev][1] > intervals[i][0]:
                if intervals[prev][1] > intervals[i][1]:
                    prev = i
                else:
                    prev = prev
                count += 1
            else:
                prev = i
        return count

「刪掉當前這個」對應的動作就是 prev 不動 —— 讓它繼續代表那個結束比較早的區間。上面寫成 prev = prev 只是為了讓兩個分支對稱，實際可以整段拿掉。

寫法二：按結束時間排序

前面的區間題都是按開始時間排的，這題剛好可以看看按結束時間排會怎樣：

class Solution:            
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[1], x[0]))
        end = intervals[0][1]
        keep = [intervals[0]]
        for i in range(1, len(intervals)):
            if intervals[i][0] >= end:
                # 找到下一個沒有重疊的區間
                end = intervals[i][1]
                keep.append(intervals[i])
            else:
                # 有重疊就跳過，等於刪掉它
                continue

        return len(intervals) - len(keep)

兩種寫法的差別值得留意：按開始時間排的時候，「該刪哪一個」需要一個內層 if 來判斷；按結束時間排的時候，這個決定已經被排序做掉了 —— 排在前面的天然就是結束比較早的，所以只剩「不重疊就留、重疊就跳過」一個分支。

選對排序的 key，可以把一整個分支消掉。 這也是為什麼區間類的貪心題，第一件事是想清楚要按哪一端排序。

補充

跟 452. Minimum Number of Arrows 只差一個等號。 兩題都是在數「最多有幾段互不重疊」，唯一的差異是端點相接算不算重疊：

	[1,2] 和 [2,3]	判斷式
435	不算重疊，兩個都能留	intervals[i][0] >= end
452	算重疊，一箭能同時射破	intervals[i][0] > end

動手前先確認這件事，不然整題邏輯對、答案差 1。

區間家族：

題目	問什麼	排序的 key
252. Meeting Rooms	有沒有重疊	開始
56. Merge Intervals	把重疊的併起來	開始
57. Insert Interval	插入一段後重新合併	已排序
253. Meeting Rooms II	最少幾間會議室	開始（配 heap 追最早結束）
435	最少刪幾個	結束
452. Burst Balloons	最少幾支箭	結束
986. Interval List Intersections	兩張表的交集	已排序

分界很清楚：問「有沒有 / 併起來」按開始排，問「最多能留幾個 / 最少要幾個」按結束排。 後者才是貪心，前者只是掃描。整套見 Intervals 模板。

複雜度

• 時間 $O(n\log n)$ — 排序主導，後面的掃描只有 $O(n)$
• 空間 $O(1)$ — 指針版只有 prev 和 count（不計 Python sort 本身最壞 $O(n)$ 的暫存）

其中 $n$ 是區間數量。上面用 keep 陣列的版本空間是 $O(n)$，但答案只需要「留了幾個」這個數字，所以那個陣列是可以省掉的。