用最少数量的箭引爆气球如何求解？（LeetCode 452）

简化版

气球在水平数轴上，每个用区间 [start, end] 表示其横向范围。一支箭从某个 x 坐标垂直射出，能引爆所有「区间覆盖了 x」的气球。求引爆全部气球所需的最少箭数。贪心策略：按右端点升序排序，一支箭尽量射在「当前这组重叠气球的最小右端点」处，能覆盖多少气球就覆盖多少；遇到左端点超过当前箭位置的气球，说明射不到了，必须再来一箭。

详细版

int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));  // 右端点升序
    int arrows = 1;                 // 至少一箭
    int arrowPos = points[0][1];    // 第一箭射在第一个气球的右端
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > arrowPos) {   // 当前气球左端超过箭位置，射不到
            arrows++;                     // 需要新的一箭
            arrowPos = points[i][1];      // 新箭射在当前气球右端
        }
        // 否则当前气球能被这一箭覆盖，不动
    }
    return arrows;
}

本质：把「能被同一支箭覆盖的气球」分成尽量少的组，组数 = 箭数。
按右端点排序：箭射在「当前组最小右端点」处，能覆盖最多后续气球。
需要新箭的条件：当前气球左端 > 当前箭位置（相接 == 也能射中，不算冲突）。
复杂度：排序 O(n log n)。注意用 Integer.compare 避免 a[1]-b[1] 溢出。

完整版教学

一、题目本质：把气球分成最少的「可共箭」组

一支箭射在坐标 x，能引爆所有覆盖 x 的气球。问题等价于：把所有区间划分成最少的若干组，每组内的区间存在一个公共点（都覆盖某个 x），组数就是最少箭数。 这和「无重叠区间 435」是同一个区间调度模型的两面——435 求最多不重叠区间，452 求最少覆盖组数，都靠「按右端点排序贪心」。

二、贪心：箭射在当前组的最小右端点

按右端点升序排序后，从左到右处理气球：

第一箭射在第一个气球的右端点 points[0][1]。为什么是右端点？因为要让这一箭尽量覆盖后面更多气球，射得越靠右越好，但又不能超过当前气球的右端（否则射不中它）——所以射在「当前这组里最小的右端点」正好卡在能覆盖最多后续气球的位置。
继续看后面的气球：只要它的左端 <= 当前箭位置，就说明它覆盖了箭所在的 x，能被这一箭引爆，跳过。
一旦某个气球的左端 > 当前箭位置，说明这一箭够不到它，必须再来一箭，新箭射在这个气球的右端点，开启新的一组。

三、为什么按右端点排、射在右端点

关键洞察：排序后遍历，「当前箭位置」始终是当前这组气球里最靠左的右端点。因为按右端点升序，先遇到的气球右端点更小，箭定在它这里。后续气球只要左端不超过这个位置，就一定和当前组有公共点（它们右端更大、左端又 ≤ 箭位置，必然覆盖箭位置）。射在最小右端点，是「既能中当前气球、又尽量靠右多覆盖后续」的最优点——这就是贪心选择。

四、和无重叠区间 435 的异同

	无重叠区间 435	射气球 452
求什么	最多保留的不重叠区间数（再算删除数）	最少箭数（= 最少覆盖组数）
排序	右端点升序	右端点升序
相接是否冲突	不算重叠（`[1,2]`,`[2,3]` 可共存）→ 用 `>=`	算能共箭（`[1,2]`,`[2,3]` 一箭射 x=2）→ 用 `>` 才需新箭

两题模型相同，唯一区别是「端点相接」的语义：435 里相接的区间不重叠可都保留；452 里相接的气球能被同一箭（射在公共端点）引爆。所以判断条件一个用 >=、一个用 >。理解这点，两题就通了。

五、易错点

易错 1：用 a[1] - b[1] 排序溢出。气球坐标可能是 Integer.MIN_VALUE/MAX_VALUE，相减会溢出。必须用 Integer.compare(a[1], b[1])。
易错 2：判断条件写成 >=。射气球里相接能共箭，只有 左端 > 箭位置（严格大于）才需新箭。写 >= 会多算箭。
易错 3：忘了初始 arrows = 1。只要有气球，至少一箭。空数组返回 0。

六、排序键、扫描不变量与边界语义

本题扫描成立的结构是：按右端升序，在当前箭位置覆盖不了新气球时新增一箭并放在新气球右端。

右端是当前气球内最靠右且仍可命中的点，给后续区间最大机会；可用交换论证替换任意更左箭位

数字推演：[10,16],[2,8],[1,6],[7,12] 排序后在6和12各射一箭，共2。

扫描过程中要始终说明已经处理部分被压缩成什么状态，以及为什么更早区间不必再看。实现边界是：气球是闭区间，所以 start≤arrow 仍被命中；坐标比较避免相减溢出。

记忆钩子：区间题先写端点语义，再选排序键；小于还是小于等于不是代码风格，而是问题定义。

七、方法对比与专项测试

问题结构	常用工具
静态合并或覆盖	排序后线性扫描
选择最多不重叠	按右端排序的贪心
最大同时重叠	扫描线或最小堆
两个有序列表求交	双指针
动态预约	有序树或线段树

测试必须覆盖空输入、单区间、完全分离、完全嵌套、链式重叠、相同起点或终点，以及端点恰好相接。若排序比较器用端点相减，还要加入整数极值检查溢出。

正确性复核要落到本题的排除逻辑：按右端升序，在当前箭位置覆盖不了新气球时新增一箭并放在新气球右端。这保证扫描指针越过某段后，它不可能再与未来候选形成更优或遗漏的答案。

已处理区间 ──压缩为边界/堆/结果尾段──> 当前区间
       │                                  │
       └─ 已由排序与端点关系证明无需回看 ─┘
当前决策完成后，指针只向右移动

在数字样例“[10,16],[2,8],[1,6],[7,12] 排序后在6和12各射一箭，共2”上，应逐轮写出被保留的边界和被丢弃的区间。若某一步无法解释为什么丢弃安全，就说明排序键、端点不等号或状态定义仍有问题。

工程上还要单独确认：气球是闭区间，所以 start≤arrow 仍被命中；坐标比较避免相减溢出。这些条件变化会直接改变重叠判定或所需数据结构，不能只修改一个比较符后沿用原证明。

八、常见误区与追问

误区：箭应射在区间中点。 中点不给后续气球最大兼容空间。
误区：端点相接需两支箭。 闭区间在共同端点可一箭命中。
误区：与无重叠区间完全不同。 数学结构相近，但端点重叠语义不同。
追问：为什么选最小右端？ 它是当前组公共交集的安全最右选择。
追问：坐标很大注意什么？ 比较器不要用 a[1]-b[1] 防溢出。
追问：复杂度是多少？ 排序 O(n log n)，扫描 O(n)。

九、加强记忆

用最少箭引爆气球 = 区间调度贪心，最少覆盖组数。按右端点升序排序，第一箭射在第一个气球右端；后续气球左端 <= 当前箭位置就被覆盖（跳过），左端 > 箭位置则 arrows++、新箭射在它右端。射在「当前组最小右端点」能覆盖最多后续。与无重叠区间 435 同模型，区别仅在相接语义：射气球相接可共箭（用 >），435 相接不重叠（用 >=）。排序用 Integer.compare 防溢出。O(n log n)。

简化版

详细版