---
title: "435. Non-overlapping Intervals"
url: "https://laigary.com/interview/coding/435-non-overlapping-intervals"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-27"
tags: ["Greedy", "Intervals", "Classic"]
---

# 435. Non-overlapping Intervals

[435\. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/)

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

## 思路

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

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

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

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

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

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

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

### 刪結束晚的那個

先看第二種情況：

```text
|-------------------|   # previous
    |----|              # current
```

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

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

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

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

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

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

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

## 解題方向

### 寫法一：按開始時間排序

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

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

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

```python
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)$：

```python
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` 只是為了讓兩個分支對稱，實際可以整段拿掉。

### 寫法二：按結束時間排序

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

```python
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](/interview/coding/452-minimum-number-of-arrows-to-burst-balloons) 只差一個等號。** 兩題都是在數「最多有幾段互不重疊」，唯一的差異是端點相接算不算重疊：

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

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

**區間家族**：

| 題目 | 問什麼 | 排序的 key |
|---|---|---|
| [252. Meeting Rooms](/interview/coding/252-meeting-rooms) | 有沒有重疊 | 開始 |
| [56. Merge Intervals](/interview/coding/56-merge-intervals) | 把重疊的併起來 | 開始 |
| [57. Insert Interval](/interview/coding/57-insert-interval) | 插入一段後重新合併 | 已排序 |
| [253. Meeting Rooms II](/interview/coding/253-meeting-rooms-ii) | 最少幾間會議室 | 開始（配 heap 追最早結束） |
| 435 | 最少刪幾個 | **結束** |
| [452. Burst Balloons](/interview/coding/452-minimum-number-of-arrows-to-burst-balloons) | 最少幾支箭 | **結束** |
| [986. Interval List Intersections](/interview/coding/986-interval-list-intersections) | 兩張表的交集 | 已排序 |

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

## 複雜度

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

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