：一箭双雕的快乐——「用最少数量的箭引爆气球」)
哈喽各位，我是前端小L。
欢迎来到贪心算法专题第十一篇！
想象一下，墙上贴着一排气球，每个气球都有一个水平覆盖范围 [start, end]。
你是神射手，可以垂直射出一支箭。只要箭的 X 坐标在气球的覆盖范围内，气球就会爆炸。
贪心目标： 找准所有气球重叠最密集的地方射箭，争取用最少的箭引爆所有气球。
力扣 452. 用最少数量的箭引爆气球
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
题目分析：
输入：
points数组，元素为[xstart, xend]。输出：最少箭数。
例子：[[10,16], [2,8], [1,6], [7,12]]
气球 A:
1~6气球 B:
2~8气球 C:
7~12气球 D:
10~16
如果我们乱射，可能需要 4 支箭。
但如果我们精打细算：
在
x=6射一箭：引爆 A(1~6) 和 B(2~8)。在
x=11射一箭：引爆 C(7~12) 和 D(10~16)。共需 2 支箭。
核心思维：寻找“重叠区间”
我们要想一箭穿透多个气球，这几个气球必须在垂直方向上有重叠。
问题转化为：如何找到这组气球的公共重叠区域？
第一步：排序
既然是区间，肯定要让它们有序排列才能方便判断。我们通常按起始位置 (Start) 从小到大排序。
排序前：
[[10,16], [2,8], [1,6], [7,12]]排序后：
[1,6], [2,8], [7,12], [10,16]
第二步：遍历与更新边界
我们拿第一支箭去瞄准第一个气球 [1, 6]。理论上，这支箭可以射在 1 到 6 之间的任何位置。
为了让这支箭能射中后面更多的气球，我们应该尽可能往右边射（延迟射出），但不能超过 6。
看第二个气球
[2, 8]：它的起始位置
2小于第一个气球的结束位置6。说明有重叠！这支箭可以同时射中这两个。
关键点：但这支箭的射击范围被压缩了。它必须在
[1, 6]里，也必须在[2, 8]里。所以这支箭最远只能射到min(6, 8) = 6。更新当前重叠组的右边界：
right = 6。
看第三个气球
[7, 12]：它的起始位置
7大于当前重叠组的右边界6。说明断档了！前面那支箭最远只能射到 6，根本够不着 7。
决策：前面的气球结算，必须射出一支箭了（
arrows++）。然后我们拿出一支新箭，瞄准这个新气球[7, 12]。
算法流程 (JavaScript)
特判：如果数组为空，返回 0。
排序：按
start(下标0) 升序排列。初始化：
arrows = 1(只要有气球，至少要一箭)。遍历：从第 2 个气球 (
i=1) 开始遍历。如果
当前气球.start > 上一个气球.end：无重叠，需要一支新箭。
arrows++。
如果
当前气球.start <= 上一个气球.end：有重叠，省下一支箭。
核心操作：更新当前气球的右边界（模拟求交集）。
当前气球.end = Math.min(当前气球.end, 上一个气球.end)。注：这里我们直接修改数组元素的 end 值，让它作为“当前重叠组的最小右边界”传递给下一次比较。
代码实现
JavaScript
/** * @param {number[][]} points * @return {number} */ var findMinArrowShots = function(points) { if (points.length === 0) return 0; // 1. 按起始位置升序排列 // 注意：a[0] - b[0] 可能会溢出(在C++中)，但在JS中 number 是浮点数，一般没事 // 稳妥写法是 (a, b) => a[0] - b[0] points.sort((a, b) => a[0] - b[0]); let arrows = 1; // 至少需要一支箭 // 2. 从第二个气球开始遍历 for (let i = 1; i < points.length; i++) { // 如果当前气球的左边界 > 上一个气球(修正后)的右边界 // 说明完全不沾边，必须新加一支箭 if (points[i][0] > points[i - 1][1]) { arrows++; } else { // 说明有重叠，这支箭可以继续穿透 // 但是，为了能穿透这两个气球，箭必须射在两者较小的那个右边界之内 // 我们更新当前气球的右边界，作为这一组重叠气球的“最远射击位置” points[i][1] = Math.min(points[i][1], points[i - 1][1]); } } return arrows; };深度辨析：为什么要Math.min？
假设气球是A: [1, 10](很大),B: [2, 3](很小且在A内部)。
排序后：A 在前，B 在后。
遍历到 B 时，
B.start(2) <= A.end(10)，有重叠。如果我们不更新边界，继续用
A.end(10)跟后面的气球比。假设后面有个气球
C: [4, 5]。C.start(4) <= A.end(10)，看起来好像能一箭穿 A、B、C？错！你的箭如果要穿过 B，就必须在
[2, 3]之间射。如果你在4射箭，虽然能中 A 和 C，但 B 就漏了。所以，一旦发现重叠，这支箭的有效射击范围就瞬间缩小到了重叠区域（即右边界取最小值
3）。这样对比 C 的时候，4 > 3，我们就知道 C 必须用新箭了。
复杂度分析
时间复杂度：$O(N \log N)$。因为有排序。遍历只需要 $O(N)$。
空间复杂度：$O(1)$。除了排序可能需要的栈空间，我们没有使用额外数组。
总结：区间问题的通解
这道题展示了区间问题的标准模板：
排序（通常按 Start 排序）。
判断重叠（Start vs PrevEnd）。
更新边界（取 Min 还是 Max 看具体需求）。
下一题预告：无重叠区间
如果你理解了这一题，那么下一题 LC 435. 无重叠区间 你只需要改两行代码就能通过。
题目问：给定一堆区间，最少移除几个区间，才能让剩下的区间都不重叠？
思考一下：
“最少移除几个”是不是等价于“最多保留几个（不重叠的）”？
而“最多保留几个不重叠的区间”是不是和“最少用几支箭引爆所有气球”有着某种神秘的数学联系？（提示：其实就是一模一样的题！）
下期见！
