LeetCode 452. 用最少数量的箭引爆气球
目录
题目描述
题意分析
平面上有若干气球，第
i个气球在 x 轴上的水平投影是闭区间[start, end]。一支箭从某个 x 坐标垂直射出，可以把所有满足start <= x <= end的气球一并引爆。问最少需要几支箭才能引爆全部气球。要什么：一个最小的射击点集合，使每个区间都至少包含集合里的一个点。气球的纵向位置、射箭的先后顺序都不影响答案，题目实质上只关心区间与点的包含关系。
约束信号有三条。第一，区间是闭区间，端点重合也算命中，
[1, 2]和[2, 3]可以被x = 2一箭双雕。第二，端点取值覆盖 32 位整型的整个范围，包含负数和极值，两个端点相减会溢出。第三，气球数量可以到十万量级，任何 $O(n^2)$ 的两两求交都不可行。边界包括：只有一个气球；所有气球完全重合；所有气球两两不相交；相邻两个区间恰好共享一个端点。
解法：按右端点排序贪心
核心思路
把气球看作闭区间，问题就是选择尽量少的点，使每个区间至少包含一个点。将区间按右端点升序排列：遇到第一个尚未覆盖的区间时，把新箭放在它的右端点。这个位置既能命中当前区间，又是当前允许的最靠右位置，最有机会覆盖后续区间。
扫描时维护不变量：已遍历区间全部被覆盖，
arrowPos是最后一支箭的位置。对新区间[start, end]，若start <= arrowPos，排序保证arrowPos <= end，当前箭仍在区间内；若start > arrowPos，当前箭无法覆盖它，必须新增一支箭。交换证明：设右端点最小的区间为
[s, e]。任意最优方案都必须有一支箭p落在该区间内。把p移到e不会丢失它原先覆盖的区间：那些区间的左端点不大于p，因此不大于e；其右端点又不小于全局最小右端点e。所以总能把某个最优方案调整为先在e射箭，递归处理剩余区间，贪心最优。
解题步骤
- 空数组直接返回 0。
- 按右端点升序排序；Java 比较器使用
Integer.compare，避免端点相减溢出。- 第一支箭放在第一个区间的右端点，箭数初始化为 1。
- 继续扫描；仅当新区间左端点严格大于
arrowPos时，新增一支箭并放在新区间右端点。- 返回箭数。
[[10,16],[2,8],[1,6],[7,12]]排序后为[[1,6],[2,8],[7,12],[10,16]]。箭先放在 6，覆盖前两个区间；遇到[7,12]时新增一箭放在 12，并覆盖最后两个区间，答案为 2。
代码实现
import java.util.Arrays;
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, (first, second) -> Integer.compare(first[1], second[1]));
int arrows = 1;
int arrowPos = points[0][1];
for (int idx = 1; idx < points.length; idx++) {
// 闭区间中 start <= arrowPos 仍然能被当前箭引爆。
if (points[idx][0] > arrowPos) {
arrows++;
arrowPos = points[idx][1];
}
}
return arrows;
}
}
import "sort"
func findMinArrowShots(points [][]int) int {
if len(points) == 0 {
return 0
}
sort.Slice(points, func(i int, j int) bool {
return points[i][1] < points[j][1]
})
arrows := 1
arrowPos := points[0][1]
for idx := 1; idx < len(points); idx++ {
// 闭区间中 start <= arrowPos 仍然能被当前箭引爆。
if points[idx][0] > arrowPos {
arrows++
arrowPos = points[idx][1]
}
}
return arrows
}
复杂度分析
- 时间复杂度：$O(n \log n)$，排序占主导，扫描为 $O(n)$。
- 空间复杂度：贪心扫描为 $O(1)$；计入库排序，Java 最坏为 $O(n)$，Go 为 $O(\log n)$ 调用栈。
关键点总结
- 按右端点排序，才能为第一个未覆盖区间立即确定最靠右的安全箭位。
- 闭区间端点也算命中，因此只有
start > arrowPos才需要新箭。- 已覆盖新区间时不能移动
arrowPos，否则可能失去对之前区间的覆盖。- 与 435 题“无重叠区间”使用同一贪心骨架：都是按最早结束位置保留最大余地。
易错点总结
- 比较器用
a[1] - b[1]：端点接近整型极值时会溢出，必须使用安全比较函数。- 判定写成
start >= arrowPos：[1,2]与[2,3]会被误算成需要两支箭。- 按左端点排序却仍把箭放在首区间右端点：
[1,10]、[2,3]、[4,5]会错误地返回 1。- 区间被覆盖时更新箭位：可能把箭移出此前区间，例如
[1,6]、[2,8]、[7,12]。- 未处理空数组就读取
points[0]：会直接下标越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 435. 无重叠区间 | 中等 | 最少删除数使区间不重叠 |
| 646. 最长数对链 | 中等 | 最长两两不相交的链 |
| 757. 设置交集大小至少为2 | 困难 | 每个区间至少覆盖两点 |
| 1024. 视频拼接 | 中等 | 最少区间数覆盖整段 |