452. 用最少数量的箭引爆气球
题目描述
墙上贴着若干气球。points[i] = [x_start, x_end] 表示第 i 个气球在水平方向上覆盖的范围，它的竖直位置未知。
可以在任意横坐标 x 处竖直向上射箭，箭会一直飞下去，凡满足 x_start <= x <= x_end 的气球都会被射破。箭的数量不限。
返回让所有气球都破掉所需的最少箭数。
示例 1
输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2
解释：在 x = 6 射一箭破 [2,8] 和 [1,6]，在 x = 11 射一箭破 [10,16] 和 [7,12]。
示例 2
输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4
解释：四个气球互不相交，每个都要单独一箭。
示例 3
输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2
解释：在 x = 2 和 x = 4 各射一箭即可，端点相同也能同时射破。
数据范围
1 <= points.length <= 10^5points[i].length == 2-2^31 <= x_start < x_end <= 2^31 - 1
解题思路
按右端点从小到大排序。第一支箭射在第一个气球的右端点 end：这是能射中它的最靠右位置，能顺带射中尽可能多的后续气球。依次检查后面的气球：起点 a ≤ end 说明已经被这支箭射中；a > end 说明射不到，需要新箭，射在这个气球的右端点。
为什么正确
end 是当前这支箭的位置，所有右端点不超过 end 的气球都已被某支箭射中，且已用的箭数是最少的。
复杂度分析
时间 O(n log n)，空间 O(log n)（排序栈）。
易错点
区间是闭区间，起点等于 end 时也能射中，所以判断条件是 a > end 而不是 a >= end。比较器不要写 x[1] - y[1]，坐标可达 ±2^31，相减会溢出。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda p: p[1])
arrows = 1
end = points[0][1]
for a, b in points[1:]:
if a > end:
arrows += 1
end = b
return arrowsclass Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (x, y) -> Integer.compare(x[1], y[1]));
int arrows = 1;
long end = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}
}class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), [](const vector<int>& x, const vector<int>& y) { return x[1] < y[1]; });
int arrows = 1;
long end = points[0][1];
for (size_t i = 1; i < points.size(); i++) {
if (points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}
};func findMinArrowShots(points [][]int) int {
sort.Slice(points, func(i, j int) bool { return points[i][1] < points[j][1] })
arrows := 1
end := points[0][1]
for _, p := range points[1:] {
if p[0] > end {
arrows++
end = p[1]
}
}
return arrows
}var findMinArrowShots = function(points) {
points.sort((x, y) => x[1] - y[1]);
let arrows = 1;
let end = points[0][1];
for (const [a, b] of points.slice(1)) {
if (a > end) {
arrows++;
end = b;
}
}
return arrows;
};function findMinArrowShots(points: number[][]): number {
points.sort((x, y) => x[1] - y[1]);
let arrows = 1;
let end = points[0][1];
for (const [a, b] of points.slice(1)) {
if (a > end) {
arrows++;
end = b;
}
}
return arrows;
}