452. Minimum Number of Arrows to Burst Balloons

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

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

建議先看 435. Non-overlapping Intervals，兩題數的是同一個數字。

思路

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

接著是這題的核心等式：

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

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

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

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

箭要射在哪裡

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

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

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

為什麼往右挪不會射漏

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

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

原本 $x$ 打得到 $i$ ，代表 $s t a r t_{i} \leq x$ ，而 $x \leq e_{1}$ ，所以 $s t a r t_{i} \leq e_{1}$ ✓
又因為 $e_{1}$ 是最小的結束座標，所以 $e_{1} \leq e n d_{i}$ ✓

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

所以「把箭放在最小的 end 上」永遠不會比最佳解差，可以放心地一步一步決定下去。更多這類判斷見 Greedy 模板。

端點相接算重疊

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

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

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

解題方向

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	不算重疊	`points[i][0] >= right`
452	算重疊（一箭雙鵰）	`points[i][0] > right`

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

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

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

複雜度

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

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