有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1：
代码语言：javascript复制输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。示例 2：
代码语言：javascript复制输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。示例 3：
代码语言：javascript复制输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。 题目分析
这个题目有点绕，这道题要求的是引爆所有气球最少的弓箭数，根据贪心策略，那么我们要把每支弓箭的价值最大化。即一只弓箭要引爆尽可能多的气球。 因此，一支箭如果要射爆多个气球，这些气球应该满足什么条件？ 根据题目意思，箭的发射位置要在气球的范围内就能引爆该气球。因此弓箭要引爆多个气球，弓箭的发射点就必须要在每个气球的范围内。即这些气球范围要有交集。 求两个区间的交集
判断两个区间是否有交集 排序两个区间，必然有一个区间靠前[start_i, end_i]，一个区间靠后[start_j, end_j]; 靠前区间的终点小于靠后区间的起点end_i < start_j，则两个区间没有交集； 否则，两个区间有交集；
题目分析
这个题目有点绕，这道题要求的是引爆所有气球最少的弓箭数，根据贪心策略，那么我们要把每支弓箭的价值最大化。即一只弓箭要引爆尽可能多的气球。 因此，一支箭如果要射爆多个气球，这些气球应该满足什么条件？ 根据题目意思，箭的发射位置要在气球的范围内就能引爆该气球。因此弓箭要引爆多个气球，弓箭的发射点就必须要在每个气球的范围内。即这些气球范围要有交集。 求两个区间的交集
判断两个区间是否有交集 排序两个区间，必然有一个区间靠前[start_i, end_i]，一个区间靠后[start_j, end_j]; 靠前区间的终点小于靠后区间的起点end_i < start_j，则两个区间没有交集； 否则，两个区间有交集；
求解两个区间的交集 区间交集的起点为两个区间中起点较大的，即max(start_i, start_j)； 区间交集的终点为两个区间中终点较小值，即min(end_i, end_j);
求区间的交集个数
我们对所有的气球区间进行排序，维护当前的区间交集[start, end]。
如果当前区间与当前区间交集还有交集，那么更新交集区间； 否则当前区间和之前的区间没有交集，之前的交集使用一根箭；自己作为新的区间交集，去找和其他区间的交集；
从图中可以看出，我们在找到与当前区间交集没有交集的区间时，更新箭数；而最后一个交集在遍历结束时直接退出没有更新箭数，因此最后遍历结束后还需要手动 1；
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end()); // 根据区间起点进行升序排序，起点相同根据终点升序排序【保证靠前的区间在前面】
int arrow = 0; // 使用的箭数
int start = points[0][0]; // 区间交集起点，初始为首个区间起点
int end = points[0][1]; // 区间交集终点，初始为首个区间终点
// 从第二个区间开始遍历
for(int i = 1; i < points.size(); i ){
if(points[i][0] > end){
// 当前区间与当前区间交集没有交集，当前区间交集使用一根箭；更新区间交集为当前区间
arrow ;
start = points[i][0];
end = points[i][1];
}else{
// 当前区间与当前区间交集有交集，更新区间交集
start = max(start, points[i][0]);
end = min(end, points[i][1]);
}
}
arrow ; // 最后一个区间交集还需要使用一根箭
return arrow;
}
};
