---
title: "452. Minimum Number of Arrows to Burst Balloons"
url: "https://laigary.com/interview/coding/452-minimum-number-of-arrows-to-burst-balloons"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-27"
tags: ["Greedy", "Intervals", "Classic"]
---

# 452. Minimum Number of Arrows to Burst Balloons

[452\. Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/)

給一堆氣球的水平範圍 `[start, end]`，一支箭從座標 `x` 垂直射上去，會射破所有滿足 `start ≤ x ≤ end` 的氣球。問最少要幾支箭才能把氣球全部射破。

建議先看 [435. Non-overlapping Intervals](/interview/coding/435-non-overlapping-intervals)，兩題數的是同一個數字。

## 思路

**先把題目翻譯掉**：氣球的寬度就是一個區間，一支箭就是一個座標。「射破所有氣球」＝「選出最少的座標，讓每個區間至少被一個座標打到」。

接著是這題的核心等式：

```text
最少需要的箭數  =  最多有幾個彼此完全不重疊的區間
```

**為什麼會相等？** 兩邊各推一次：

- **至少要這麼多**：如果有 $k$ 個區間彼此完全沒有交集，那它們兩兩沒有共同座標，一支箭不可能同時打到其中兩個 —— 所以至少需要 $k$ 支
- **這麼多就夠了**：下面的貪心真的只用了 $k$ 支

上下界夾在一起，答案就是 $k$。這就是為什麼這題跟 435 是同一個核心：435 問「最多能留幾個不重疊的」，452 問「最少要幾支箭」，數的是同一件事。

### 箭要射在哪裡

貪心的動作是：**按結束座標排序，每支箭都射在「當前這批還沒被射破的氣球中，最早結束的那一顆」的右端點上。**

為什麼是右端點？因為箭的位置只要合法（打得到目標氣球），就該**盡量往右擺** —— 越靠右越有機會順便打到後面的氣球。而合法範圍的最右邊，就是這顆氣球的 `end`，再往右一格就打不到它了。

排序之後，第一顆氣球的 `end` 就是所有氣球裡最小的，所以第一支箭一定射在那裡。

### 為什麼往右挪不會射漏

這題的交換論證特別乾淨。設排序後第一顆氣球是 $B_1$，它的結束座標 $e_1$ 是全部氣球裡最小的。

任何一個合法解裡，一定有某支箭 $x$ 打到了 $B_1$，也就是 $x \le e_1$。現在把這支箭往右挪到 $e_1$，檢查有沒有射漏任何原本打得到的氣球 $i$：

- 原本 $x$ 打得到 $i$，代表 $start_i \le x$，而 $x \le e_1$，所以 $start_i \le e_1$ ✓
- 又因為 $e_1$ 是**最小**的結束座標，所以 $e_1 \le end_i$ ✓

兩個條件都成立，代表 $e_1$ 一樣打得到氣球 $i$。**往右挪只會增加涵蓋範圍，不可能減少。**

所以「把箭放在最小的 `end` 上」永遠不會比最佳解差，可以放心地一步一步決定下去。更多這類判斷見 [Greedy 模板](/interview/coding/greedy-template)。

### 端點相接算重疊

這一點跟之前的區間題不一樣，要特別留意。

前面的題目遇到 `prev[1] == curr[0]`（前一段的結束剛好等於後一段的開始）算**不重疊**；但在這題，箭射在那個共同座標上可以**同時射破兩顆氣球**，所以要算成重疊、共用一支箭。

也就是說，要另外開一支箭的條件是「前一顆的結束座標**完全小於**現在這顆的開始座標」。

## 解題方向

```python
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        
        points.sort(key = lambda x: x[1])
        right = points[0][1]
        count = 1

        for i in range(1, len(points)):
            if right >= points[i][0]:
                continue
            else:
                right = points[i][1]
                count += 1
        
        return count
```

`right` 代表**最後射出的那支箭的座標**。`right >= points[i][0]` 就是「這顆氣球的左端在箭的左邊或剛好對齊」，代表現有的箭已經打到它了，`continue` 跳過。否則就得開一支新箭，射在這顆氣球的右端。

`count` 從 1 開始而不是 0，因為排序後第一顆氣球一定需要一支箭。也因為這樣，`points[0]` 直接取用是安全的 —— 題目保證至少有一顆氣球。

## 補充

**跟 435 只差一個等號。** 兩題都在數「最多有幾段互不重疊」，程式碼結構完全一樣，差別只有端點相接怎麼算：

| | `[1,2]` 和 `[2,3]` | 要開新的一支 / 保留一個的條件 |
|---|---|---|
| [435. Non-overlapping Intervals](/interview/coding/435-non-overlapping-intervals) | **不**算重疊 | `points[i][0] >= right` |
| 452 | 算重疊（一箭雙鵰） | `points[i][0] > right` |

動手前先確認題目對「剛好碰到」的定義，不然邏輯全對、答案差 1。

**為什麼不能按開始座標排序？** 按開始排的話，遇到重疊時還要多一層判斷「該留哪一顆」（435 的第一種寫法就是這樣）。按結束排序等於把這個決定交給排序做掉了 —— 排在前面的天然就是結束最早的，於是只剩一個分支。整套區間題的排序 key 對照見 [Intervals 模板](/interview/coding/intervals-template)。

**同一個貪心形狀的其他題**：[1024. Video Stitching](/interview/coding/1024-video-stitching)（用最少的片段覆蓋 `[0, time]`）、[253. Meeting Rooms II](/interview/coding/253-meeting-rooms-ii)（永遠找最早結束的那間會議室）。共同點都是「結束得越早，留給後面的空間越大」。

## 複雜度

- 時間 $O(n \log n)$ — 排序主導，後面只掃一次 $O(n)$
- 空間 $O(1)$ — 只有 `right` 和 `count` 兩個變數（不計 Python `sort` 本身最壞 $O(n)$ 的暫存）

其中 $n$ 是氣球的數量。