题目描述
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
样例
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
输入：points = [[2,3],[2,3]]
输出：1
算法1
(暴力枚举) $O(n)$
思路: 只要一个区间和另一个区间有子区间重合，那这两个区间就可以用同一只箭.
所以如何判断区间之间有子区间重合？
为了方便在一次遍历中识别重合，先进行排序，那么是按区间左端还是右端排升序呢？
如果按左端升序排序，可能出现这种：[0, 9], [0, 6], [7, 8]
· 当前第一个区间和第二个重合，我让当前第一个区间继续寻求重合，它和第三个也重合。
· 你想着一箭三雕，但第二个和第三个其实并不重合。
· 被「包含」在当前区间的重合区间，不一定和别的重合区间重合
· 当前区间可能和很多人重合，但无法保证内部都互相重合。
如果按右端升序排序，就杜绝了「前面包后面」的情况。
如上图，当前区间遇到重合区间 a，a 的右端>=当前区间的右端（因为右端递增），遇到下一个重合区间 b，b 的左端<=自己的右端（因为有重合），所以a、b 一定有交集，参照的是当前区间的右端。
于是，放心地让当前区间一路找重合，直到遇到不重合，就有了一组能一箭穿的。
当按照按右端升序排列的话,并且以: 当前区间的右端 >= 后面区间的左端 作为区间重合的标志。在极端情况下:
当前区间的右边界 == 下一个区间的有边界,那也必然存在当前区间的右端 >= 下一个区间的左端这个条件,达到这个条件就说明这两个区间重合
示例:
1.拿当前区间的右端作为标杆。
2.只要 下一个区间的左端<=标杆下一个区间的左端<=标杆下一个区间的左端<=标杆，则重合，继续寻求与下一个区间重合。
3.直到遇到不重合的区间，弓箭数 +1。
4.拿新区间的右端作为标杆，重复以上步骤
时间复杂度
O(n)
参考文献
Java 代码
class Solution {
public int findMinArrowShots(int[][] points) {
if(points == null) return 0;
Arrays.sort(points,(o1,o2) -> Integer.compare(o1[1],o2[1]));
int count = 0;
int i = 0;
while(i < points.length){
//当前i 区间的右端作为标志位
int flag = points[i][1];
i ++;
while(i < points.length && points[i][0] <= flag){
i++;
}
//从上面的while 循环出来,说明当前i 区间并不和之前的区间重合,那之前的区间都可以用同一只箭
//下一次就用这个i 区间作为标志位
count ++;
}
return count;
}
}
