452. Minimum Number of Arrows to Burst Balloons

題目 / Problem

中文： 牆上貼著一些球形氣球。每個氣球用一個區間 points[i] = [x_start, x_end] 表示，代表它的水平直徑從 x_start 延伸到 x_end。你可以從 x 軸上任意位置朝正上方（垂直）射出箭。如果一支箭射在位置 x，且某個氣球滿足 x_start <= x <= x_end，那這個氣球就會被射爆。一支箭會無限往上飛，沿途的所有氣球都會被射爆。請回傳「射爆所有氣球所需的最少箭數」。

English: Balloons are taped to a wall. Each balloon is given as an interval points[i] = [x_start, x_end], its horizontal diameter. You may shoot arrows straight up from any x-coordinate. An arrow shot at x bursts a balloon if x_start <= x <= x_end. An arrow keeps traveling upward forever, bursting every balloon in its vertical path. Return the minimum number of arrows needed to burst all balloons.

Constraints / 限制條件： - 1 <= points.length <= 10^5 - points[i].length == 2 - -2^31 <= x_start < x_end <= 2^31 - 1 （注意：端點可能逼近 32 位整數的極值 / endpoints can reach the limits of a 32-bit integer）

Worked example / 範例：

Input:  points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2

一支箭射在 x = 6 可同時爆掉 [2,8] 和 [1,6]；另一支射在 x = 11 可爆掉 [10,16] 和 [7,12]。所以只需 2 支箭。 One arrow at x = 6 bursts [2,8] and [1,6]; another at x = 11 bursts [10,16] and [7,12]. Total: 2 arrows.

名詞解釋 / Glossary

• 區間 / Interval： 一對數字 [start, end]，表示一段範圍。這裡每個氣球就是一個區間。An interval is a pair [start, end] describing a range; here each balloon is one interval.
• 重疊 / Overlap： 兩個區間若共享至少一個 x 值就算重疊。例如 [1,6] 和 [2,8] 在 2~6 之間重疊。Two intervals overlap if they share at least one x value (e.g. [1,6] and [2,8] share 2..6). One arrow can burst all mutually-overlapping balloons at once.
• 貪心演算法 / Greedy algorithm： 每一步都做「當下看起來最好」的選擇，而不回頭。本題每次都讓一支箭盡量射爆更多氣球。A greedy algorithm makes the locally-best choice at each step without backtracking; here, each arrow bursts as many balloons as possible.
• 排序 / Sorting： 把資料按某個鍵值由小到大排列。我們會按氣球的「右端點 x_end」排序，這是貪心成立的關鍵。Sorting arranges data by a key; we sort balloons by their right endpoint x_end, which makes the greedy choice provably correct.
• 比較函數 / Comparator： 排序時告訴程式「誰排前面」的小函數。在 C 用於 qsort，在 C++ 用於 sort。A comparator is a small function telling the sort routine which element comes first.
• 溢位 / Overflow： 當數字超過型別能表示的範圍就會「繞回」變成錯誤的值。本題端點可達 ±2^31，相減容易溢位，要小心。Overflow happens when a value exceeds what the type can hold and wraps around; endpoints near ±2^31 make subtraction dangerous, so we compare instead of subtract.

思路

中文： 先想最暴力的想法：把每個氣球單獨射爆，那就要 n 支箭。但顯然當多個氣球互相重疊時，一支箭就能一次爆掉它們，所以我們要盡量讓箭「共用」。問題變成：把氣球分成最少的幾組，使得「每組裡的氣球都有一個共同的 x 點可以被同一支箭穿過」，組數就是答案。

關鍵觀察是貪心：先把所有氣球按右端點 x_end 由小到大排序。為什麼用右端點？因為我們想讓第一支箭射得盡量靠右，這樣它就有最大機會順便爆到後面的氣球。我們把箭射在「目前這組裡最小的右端點」上——也就是第一個氣球的 x_end。接著往後掃，只要下一個氣球的左端點 x_start <= 箭的位置，代表它和這支箭重疊，可以被同一支箭爆掉，跳過即可；一旦遇到某個氣球的 x_start > 箭的位置，代表這支箭碰不到它了，就必須新開一支箭，並把箭的位置更新成這個新氣球的右端點。

為什麼把箭設在右端點是對的？因為按右端點排序後，當前這支箭的位置是這一組裡最小的右端點，任何左端點 <= 它的氣球一定與它重疊（因為氣球的左端點 < 右端點，而它的右端點又 >= 箭的位置）。這保證了每次新開箭都是「不得不開」，所以箭數最少。整體只需一次排序加一次線性掃描。

English: Start with brute force: shoot one arrow per balloon — that's n arrows. But whenever balloons overlap, a single arrow can pop all of them at once, so we want arrows to be shared. The problem becomes: partition the balloons into the fewest groups such that every balloon in a group can be pierced by one common x-coordinate. The number of groups is the answer.

The greedy insight: sort all balloons by their right endpoint x_end ascending. Why the right endpoint? We want each arrow placed as far right as it can go while still hitting the current balloon, giving it the best chance to also catch later balloons. So we place the arrow exactly at the smallest right endpoint in the current group — the first balloon's x_end. Then we scan forward: as long as the next balloon's x_start <= arrow position, it overlaps the arrow and gets burst for free, so we skip it. The moment we hit a balloon whose x_start > arrow position, this arrow can't reach it, so we must fire a new arrow and move the arrow position to that balloon's x_end.

Why is placing the arrow at the right endpoint optimal? After sorting by x_end, the current arrow sits at the smallest right endpoint of its group, so any balloon whose left endpoint is <= it must overlap (its own left < right, and its right >= the arrow). This guarantees we only ever open a new arrow when forced to, which yields the minimum count. The whole thing is one sort plus one linear pass.

逐步走查 / Walkthrough

Example input: points = [[10,16],[2,8],[1,6],[7,12]]

Step 1 — Sort by right endpoint x_end / 按右端點排序：

排序後 / sorted: [[1,6], [2,8], [7,12], [10,16]]

Step 2 — Scan and place arrows / 掃描並放箭：

Result / 結果： arrows = 2 ✓

Solution — C

// 演算法 / Algorithm:
// 1) 按右端點 x_end 由小到大排序 / Sort balloons by right endpoint ascending.
// 2) 貪心掃描：箭放在當前組的最小右端點；左端點 <= 箭位置的氣球可共用此箭，
//    否則開新箭。/ Greedy scan: place an arrow at the current group's smallest
//    right endpoint; reuse it while x_start <= arrow, else open a new arrow.

#include <stdlib.h>   // 提供 qsort / provides qsort

// 比較函數：告訴 qsort 如何排序 / Comparator telling qsort how to order two balloons.
// a、b 是 void* 指向「某一列」，每列是 int[2]。/ a,b are void* pointing to one row (int[2]).
static int cmp(const void *a, const void *b) {
    // 把 void* 轉成 int* 再取第二個數（右端點 x_end）。/ Cast to int* and read index 1 (x_end).
    // (*(const int (*)[2])a) 代表「a 指向的那一列」，[1] 取右端點。
    // Here (const int (*)[2]) means "pointer to an array of 2 ints" = one row.
    int ea = (*(const int (*)[2])a)[1];   // 第一個氣球的右端點 / first balloon's x_end
    int eb = (*(const int (*)[2])b)[1];   // 第二個氣球的右端點 / second balloon's x_end
    // 用比較而非相減，避免大數相減溢位。/ Compare (not subtract) to avoid 32-bit overflow.
    if (ea < eb) return -1;               // ea 較小排前面 / ea goes first
    if (ea > eb) return  1;               // ea 較大排後面 / ea goes later
    return 0;                             // 相等 / equal
}

int findMinArrowShots(int** points, int pointsSize, int* pointsColSize) {
    // 沒有氣球就不用箭。/ No balloons means no arrows needed.
    if (pointsSize == 0) return 0;

    // 排序：把 points 的每一列（每個氣球）按右端點排好。/ Sort rows by x_end.
    // 參數：起始位址、列數、每列大小、比較函數。/ args: base, count, element size, comparator.
    qsort(points, pointsSize, sizeof(points[0]), cmp);

    int arrows = 1;                       // 至少需要一支箭 / at least one arrow is needed
    // arrowPos 記錄目前這支箭射在哪裡 = 當前組的最小右端點。
    // arrowPos = where the current arrow is shot = current group's smallest x_end.
    long arrowPos = points[0][1];         // 用 long 保險，雖然此處比較不會溢位 / long for safety

    // 從第二個氣球開始逐一檢查。/ Check each balloon starting from index 1.
    for (int i = 1; i < pointsSize; i++) {
        // points[i][0] 是這個氣球的左端點 x_start。/ points[i][0] is this balloon's x_start.
        if (points[i][0] > arrowPos) {    // 左端點超過箭位置 → 這支箭碰不到它 / arrow can't reach it
            arrows++;                      // 必須新開一支箭 / must fire a new arrow
            arrowPos = points[i][1];       // 新箭放在這個氣球的右端點 / new arrow at this x_end
        }
        // else：x_start <= arrowPos，與當前箭重疊，被同一支箭爆掉，什麼都不用做。
        // else: it overlaps the current arrow, burst for free, nothing to do.
    }

    return arrows;                         // 回傳最少箭數 / return the minimum arrow count
}

Solution — C++

// 演算法 / Algorithm:
// 1) 按右端點 x_end 由小到大排序 / Sort balloons by right endpoint ascending.
// 2) 貪心掃描：箭放在當前組最小右端點；x_start <= 箭位置就共用，否則開新箭。
//    Greedy scan: arrow at current group's smallest x_end; reuse while x_start <= arrow.

#include <vector>      // std::vector，動態陣列 / dynamic array container
#include <algorithm>   // std::sort

class Solution {
public:
    int findMinArrowShots(std::vector<std::vector<int>>& points) {
        // points.empty() 檢查有沒有氣球。/ Check whether there are no balloons.
        if (points.empty()) return 0;

        // 用 lambda（匿名函數）當比較規則，按右端點 [1] 由小到大。
        // A lambda is an inline function; here it compares two balloons by their x_end.
        // 用 a[1] < b[1] 比較而非相減，避免大數相減溢位。
        // Compare a[1] < b[1] instead of subtracting, to avoid 32-bit overflow.
        std::sort(points.begin(), points.end(),
                  [](const std::vector<int>& a, const std::vector<int>& b) {
                      return a[1] < b[1];   // 右端點較小的排前面 / smaller x_end first
                  });

        int arrows = 1;                     // 至少一支箭 / at least one arrow
        // arrowPos：目前這支箭的位置 = 當前組最小右端點。用 long 防溢位。
        // arrowPos: current arrow position = group's smallest x_end; long for safety.
        long arrowPos = points[0][1];

        // 範圍 for 從第二個氣球開始；這裡用索引以便讀左右端點。
        // Iterate from the second balloon (index-based to read both endpoints).
        for (size_t i = 1; i < points.size(); ++i) {
            // points[i][0] 是左端點 x_start。/ points[i][0] is this balloon's x_start.
            if (points[i][0] > arrowPos) {  // 箭碰不到這個氣球 / arrow can't reach this balloon
                ++arrows;                   // 開新箭 / fire a new arrow
                arrowPos = points[i][1];    // 新箭設在此氣球右端點 / place it at this x_end
            }
            // 否則重疊，被同一支箭爆掉。/ Otherwise it overlaps and is burst for free.
        }

        return arrows;                      // 最少箭數 / minimum number of arrows
    }
};

複雜度 / Complexity

• Time: O(n log n) — n 是氣球數量。排序花 O(n log n)，是主導項；之後只掃一遍是 O(n)，所以總和由排序決定。Sorting dominates at O(n log n); the single linear scan afterward is O(n), so the total is O(n log n).
• Space: O(1) 額外空間（不計排序內部使用與輸入本身）。我們只用了 arrows、arrowPos 等幾個變數，沒有額外配置陣列。We use only a few scalar variables; no extra arrays are allocated (ignoring the sort's internal usage and the input itself).

Pitfalls & Edge Cases

• 整數溢位 / Integer overflow： 端點可達 ±2^31，若比較函數寫成 return a[1] - b[1]，兩個極值相減會溢位導致排序錯誤。本題改用 < / > 比較，完全避開減法。Endpoints reach ±2^31; subtracting them (a[1]-b[1]) overflows a 32-bit int and corrupts the sort. We compare with </> instead.
• 「邊界相接」也算重疊 / Touching endpoints count as overlap： 像 [1,2] 和 [2,3] 在 x=2 相接，仍可被同一支箭爆掉，所以判斷必須是 x_start > arrowPos 才開新箭（用 > 而不是 >=）。Intervals like [1,2] and [2,3] touch at x=2 and share an arrow, so we open a new arrow only when x_start > arrowPos (strictly greater).
• 排序鍵選錯 / Wrong sort key： 若按左端點 x_start 排序，貪心會失效，因為無法保證箭的位置是「最緊」的右界。一定要按右端點 x_end 排序。Sorting by x_start breaks the greedy proof; you must sort by x_end.
• 初始箭數 / Initial arrow count： arrows 要從 1 開始（已先放好第一支箭），不是 0，否則少算一支。Start arrows at 1 because the first arrow is already placed; starting at 0 undercounts.
• 空輸入 / Empty input： 雖然約束保證 length >= 1，程式仍先檢查 empty 回傳 0，更穩健。Constraints guarantee at least one balloon, but the empty-check returns 0 defensively.