452. 用最少数量的箭引爆气球（Minimum Number of Arrows to Burst Balloons）

频次 ★★★★ · 难度 🟡 · 高频：字节/阿里

题目

气球在水平线上，每个气球有起止坐标 [start, end]。一箭从某点垂直射出可刺破该点上的所有气球。求引爆所有气球所需的最少箭数。

示例：

输入: points = [[10,16],[2,8],[1,6],[7,12]]
输出: 2 （在 x=6 射一箭刺破 [1,6],[2,8]；在 x=11 射一箭刺破 [10,16],[7,12]）

输入: points = [[1,2],[3,4],[5,6],[7,8]]
输出: 4 （气球互不重叠，每箭只能刺破一个）

思路

贪心（按右边界排序）：与 435 无重叠区间思路完全一致。按每个气球的右边界升序排序，每次射箭选择当前气球的右边界位置，这样可以覆盖尽可能多的后续重叠气球。遍历时，如果下一个气球的左边界 > 当前箭的位置（即不重叠），需要新射一箭。

代码

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;
    // 按右边界排序，注意用 Integer.compare 避免溢出
    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) —— 排序
• 空间：O(1)

边界条件

• 空数组：返回 0
• 所有气球重叠（如 [1,10],[2,8],[3,6]）：一箭即可，返回 1
• 气球边界刚好接触（如 [1,2],[2,3]）：points[i][0] > arrowPos 用 > 而非 >=，边界接触算重叠，一箭即可
• 坐标范围大（-2^31 ~ 2^31-1）：排序时用 Integer.compare 避免 a[1] - b[1] 溢出

变式

• 435. 无重叠区间：贪心思路完全一致（按右边界排序），只是统计目标不同
• 56. 合并区间：按左边界排序，合并重叠区间

易错点

• 排序用 Integer.compare 而非 a[1] - b[1]：坐标范围是 [-2^31, 2^31-1]，a[1] - b[1] 会溢出（如 Integer.MIN_VALUE - Integer.MAX_VALUE）
• 重叠判断用 > 还是 >=：本题气球边界接触算重叠（在边界点射箭可以同时刺破），所以用 >
• 按右边界排序而非左边界：按左边界排序需要额外维护当前重叠区间的右边界最小值，不如按右边界简洁

面试追问

• 为什么按右边界排序？ 局部最优：每次射箭选当前最早结束的气球右边界，可以覆盖所有与之重叠的后续气球，留给后面的气球最大空间
• 和 435 无重叠区间的区别？ 435 求的是”最少移除区间数使剩余不重叠”，452 求的是”最少箭数引爆所有气球”，两者贪心策略完全一致，只是统计口径不同

关联题

• 同套路：435. 无重叠区间 —— 相同贪心策略
• 进阶：56. 合并区间 —— 按左边界排序
• 知识点：区间贪心模板见贪心