1.题目

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆 。可以射出的弓箭的数量没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
在x = 6处射出箭，击破气球[2,8]和[1,6]。
在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
在x = 2处发射箭，击破气球[1,2]和[2,3]。
在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示：
1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons

2.思路

（1）区间调度算法
此题思路可参考LeetCode_区间问题_中等_435.无重叠区间。

3.代码实现（Java）

//思路1————区间调度算法
public int findMinArrowShots(int[][] points) {
    //将所有区间按照其右端点的值进行升序排序
    Arrays.sort(points, (a ,b) -> {
        /*
            需要注意的是，当区间的端点值非常大或者非常小时
            相减(a[1] - b[1])可能会出现整数溢出的情况，而自定义的排序策略仅与compare()返回值的正负有关
            所以只需比较 a[1] 和 b[1] 的大小，根据比较结果返回 -1 或者 1 即可
        */
        return a[1] < b[1] ? -1 : 1;
    });
    //最少需要一支箭
    int res = 1;
    int x_end = points[0][1];
    for (int[] point : points) {
        if (x_end < point[0]) {
            //找到一个与当前区间不相交的区间
            res++;
            //更新x_end
            x_end = point[1];
        }
    }
    return res;
}