LeetCode 452 用最少数量的箭引爆气球 区间贪心

LeetCode 452. 用最少数量的箭引爆气球 —— 区间贪心经典：排序 + 扫描一箭穿心

区间问题是贪心算法中最经典的实战领域之一。今天我们将深入解析用最少数量的箭引爆气球（LeetCode 452），本质上这是一个区间重叠计数问题：给定多个区间（气球），求最少需要几个点（箭）使得每个区间至少包含一个点。

这道题与「会议室 II」（LeetCode 253）、「无重叠区间」（LeetCode 435）并称为区间贪心三兄弟——它们共享同一核心招式：排序 + 扫描。

本文将从三种思路入手：暴力枚举 → 贪心（按右端点排序） → 贪心（按左端点排序 + 合并），帮助大家彻底掌握区间重叠问题的通用解法。

问题描述

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

示例：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用 2 支箭来引爆：
  - 在 x = 6 处射箭，引爆 [2,8] 和 [1,6] 气球
  - 在 x = 11 处射箭，引爆 [10,16] 和 [7,12] 气球

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球都不重叠，需要 4 支箭。

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：[1,2] 和 [2,3] 重叠（边界相交算重叠），[3,4] 和 [4,5] 重叠。

核心思想

从"引爆"到"重叠"

一支箭能引爆哪些气球？其实就是那些区间互相重叠的气球。在数轴上画出来一目了然：

气球:  [1,6]  [2,8]  [7,12]  [10,16]
在数轴上:
1----6
  2--------8
            7----12
              10--------16
[1,6] 和 [2,8] 重叠 → 1 支箭（例如 x=6）可以同时引爆
[7,12] 和 [10,16] 重叠 → 1 支箭（例如 x=11）可以同时引爆
答案：2 支箭

关键问题来了： 如何判断哪些气球能被同一支箭解决？

贪心策略

想象你站在数轴上，手拿一把箭，希望用最少箭引爆所有气球。直觉上你会怎么做？

更精确的操作流程如下：

1. 先将所有气球按照它们的右边界升序排列
2. 第一支箭射在第一个气球的右边界上
3. 跳过所有被这支箭“穿心”的气球（即左边界 ≤ 箭的位置的区间）
4. 对下一个未被引爆的气球，重复第二步

为什么一定要按右边界排序？

若按左边界排序，箭可能射得太靠右，导致左侧的气球被遗漏。按右边界排序可保证每支箭都选在“当前能覆盖的气球中，最靠左的那个右边界”上射出——这正是贪心地让每支箭覆盖尽可能多的气球。

来看一个对比：

错误策略（按左边界）:
  气球 [1,100], [2,3], [4,5]
  按左边界排序: [1,100], [2,3], [4,5]
  射在 x=100 → 只引爆 [1,100]，还需 2 支箭，总计 3 支

正确策略（按右边界）:
  按右边界排序: [2,3], [4,5], [1,100]
  射在 x=3   → 引爆 [2,3] 和 [1,100]（因为 1 ≤ 3 ≤ 100）
  射在 x=5   → 引爆 [4,5]
  共 2 支箭

思路分析

解法一：暴力枚举法

最直接的想法：枚举所有可能的箭位置，找出能覆盖所有区间的最少箭数。但箭的位置是连续实数，无法直接枚举。不过有个重要观察：最优解中每支箭的位置一定是某个气球的右边界（否则可将其右移以覆盖更多气球）。

因此暴力法可退化为：枚举每个气球的右边界作为候选箭位，再通过集合覆盖方式找最少箭数。但这样搜下来是指数级的，不现实。

解法二：贪心法（按右端点排序）⭐ 推荐

核心观察一句话说透：

按右边界排序后，依次处理每个气球：
  - 如果当前气球已经被已有的箭引爆（左边界 ≤ 上一支箭的位置）→ 跳过
  - 否则 → 需要一支新箭，射在当前气球的右边界处

为什么射在右边界？
  → 右边界是能引爆当前气球的"最靠左"的位置——准确说是"最靠右"的最优位置：
    射在右边界，能覆盖所有与当前气球重叠且右边界更靠右的气球。

解法三：贪心法（按左端点排序 + 合并重叠区间）

换个视角：将重叠的气球合并成一个“大区间”，数一数最终有几个不重叠的大区间，就需要几支箭。

按左边界排序后：
  维护当前"重叠区域"的右边界 end
  - 如果下一个气球的左边界 ≤ end → 重叠，更新 end = min(end, 当前右边界)
  - 否则 → 新开一个重叠区域，箭数 +1

这本质上就是合并区间的一个变体——只不过合并时取右边界较小值（而非较大值），因为我们关心的是“重叠区域”的交集。

代码实现

JavaScript 版本

方法一：贪心法（按右端点排序）⭐

/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function(points) {
    if (points.length === 0) return 0;
    // 按右边界排序
    points.sort((a, b) => a[1] - b[1]);
    let arrows = 1;                // 至少需要一支箭
    let arrowPos = points[0][1];   // 第一支箭射在第一个气球的右边界
    for (let i = 1; i < points.length; i++) {
        // 如果当前气球的左边界 > 箭的位置 → 射不到，需要新箭

        if (points[i][0] > arrowPos) {
            arrows++;
            arrowPos = points[i][1]; // 新箭射在当前气球的右边界
        } // 否则：当前气球被已有箭引爆，跳过
    }

    return arrows;
};

方法二：贪心法（左端点排序 + 合并）

var findMinArrowShots = function(points) {
    if (points.length === 0) return 0;
    // 按左边界排序
    points.sort((a, b) => a[0] - b[0]);
    let arrows = 1;
    let end = points[0][1]; // 当前重叠区域的右边界
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] <= end) {
            // 重叠 → 更新重叠区域右边界（取较小值 = 交集）
            end = Math.min(end, points[i][1]);
        } else {
            // 不重叠 → 新增一支箭
            arrows++;
            end = points[i][1];
        }
    }
    return arrows;
};

Python 版本

方法一：贪心法（按右端点排序）⭐

def findMinArrowShots(points: list[list[int]]) -> int:
    """方法一：贪心法 (右端点排序)"""
    if not points:
        return 0

    # 按右边界排序
    points.sort(key=lambda x: x[1])
    arrows = 1                # 至少需要一支箭
    arrow_pos = points[0][1]  # 第一支箭的位置
    for i in range(1, len(points)):
        if points[i][0] > arrow_pos:
            arrows += 1
            arrow_pos = points[i][1]
    return arrows

方法二：贪心法（按左端点排序 + 合并重叠区间）

def findMinArrowShots(points: list[list[int]]) -> int:
    """方法二：贪心法 (左端点排序 + 合并重叠区间)"""
    if not points:
        return 0
    points.sort(key=lambda x: x[0])
    arrows = 1
    end = points[0][1]  # 当前重叠区域的右边界
    for i in range(1, len(points)):
        if points[i][0] <= end:
            end = min(end, points[i][1])
        else:
            arrows += 1
            end = points[i][1]
    return arrows

逐步推演

以points = [[10,16],[2,8],[1,6],[7,12]]为例（正确答案应为 2）。

方法一（按右端点排序）推演

排序前: [[10,16],[2,8],[1,6],[7,12]]
按右边界排序后: [[1,6],[2,8],[7,12],[10,16]]
初始化: arrows = 1, arrowPos = 6

=== i=1: 气球 [2,8] ===
  points[1][0] = 2 > arrowPos(6)? → 否
  2 ≤ 6，气球被箭引爆，跳过
  arrows = 1, arrowPos = 6

=== i=2: 气球 [7,12] ===
  points[2][0] = 7 > arrowPos(6)? → 是！
  7 > 6，箭射不到，需要新箭 
  arrows = 2, arrowPos = 12

=== i=3: 气球 [10,16] ===
  points[3][0] = 10 > arrowPos(12)? → 否
  10 ≤ 12，气球被箭引爆，跳过
  arrows = 2, arrowPos = 12

结果：arrows = 2

验证一下：

第1支箭 x=6:
  [1,6]:  1 ≤ 6 ≤ 6    引爆
  [2,8]:  2 ≤ 6 ≤ 8    引爆
  [7,12]: 7 ≤ 6?        射不到
  [10,16]: 10 ≤ 6?      射不到

第2支箭 x=12:
  [7,12]:  7 ≤ 12 ≤ 12   引爆
  [10,16]: 10 ≤ 12 ≤ 16  引爆

两支箭引爆全部气球

方法二（按左端点排序 + 合并）推演

排序前: [[10,16],[2,8],[1,6],[7,12]]
按左边界排序后: [[1,6],[2,8],[7,12],[10,16]]
初始化: arrows = 1, end = 6（第一个气球的右边界）

=== i=1: 气球 [2,8] ===
  points[1][0] = 2 ≤ end(6)? → 是
  重叠！更新 end = min(6, 8) = 6
  arrows = 1

=== i=2: 气球 [7,12] ===
  points[2][0] = 7 ≤ end(6)? → 否！
  不重叠！新增箭 
  arrows = 2, end = 12

=== i=3: 气球 [10,16] ===
  points[3][0] = 10 ≤ end(12)? → 是
  重叠！更新 end = min(12, 16) = 12
  arrows = 2

结果：arrows = 2

边界情况推演：端点相切

用points = [[1,2],[2,3],[3,4],[4,5]]测试（答案 2）。

按右边界排序: [[1,2],[2,3],[3,4],[4,5]]
初始化: arrows = 1, arrowPos = 2

=== i=1: [2,3] ===
  2 > 2? → 否（等于不算大于）
  重叠  arrows = 1

=== i=2: [3,4] ===
  3 > 2? → 是！
  新箭  arrows = 2, arrowPos = 4

=== i=3: [4,5] ===
  4 > 4? → 否
  重叠  arrows = 2

结果：2

复杂度分析

举一反三

关联题目

区间贪心通用框架

区间问题三步走：
1. 排序 → 按左端点或右端点（依问题而定）
2. 扫描 → 维护当前区间的"边界"
3. 判断 → 重叠？合并？计数？

本题：按右端点排序 → 扫描 → 重叠则跳过，不重叠则 +1
435：按右端点排序 → 扫描 → 重叠则移除，不重叠则保留
56：  按左端点排序 → 扫描 → 重叠则合并，不重叠则输出
253：按开始时间排序 → 扫描 → 用最小堆维护会议室结束时间

总结

一道题，三种理解：

1. 按右端点排序：最直觉——每支箭射在能引爆当前气球的最靠左位置（右边界），最大化覆盖
2. 按左端点排序+合并：与合并区间统一框架——重叠区域取交集（min），不重叠则新开一支箭
3. 本质是区间重叠计数：与 253（会议室 II）、435（无重叠区间）属于同一类问题

区间贪心的核心口诀：先排序，再扫描；判重叠，定数量。牢记此诀，再遇区间类题目，心中不慌。