90、贪心-LeetCode-452.用最少数量的箭引爆气球

题目描述：

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

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

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

来源：力扣（LeetCode）

思路：

1）将尾部排序，每次从尾部射箭，下次从还没有引爆的第一个气球的尾部继续！

每次在坐标轴上走尽可能大的距离！在这个前提下，有可能已经引爆了其他气球！就跳过这些气球，继续往下找！

2)二维数组比较的写法：

        Arrays.sort(points,new Comparator(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] < o2[1]) return -1;
                else return 1;
            }
        });

Arrays.sort(points, (p1, p2) -> p1[1] < p2[1] ? -1 : 1);

代码：

1）排序 + 贪心：

class Solution {
    public int findMinArrowShots(int[][] points) {
        
        //区间有重叠，就会一只箭全部射穿
        //二维数组的排序需要使用 比较器
        int res = 0;//记录多少箭

        //按照尾部排序，头部不用处理
        Arrays.sort(points,new Comparator(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] < o2[1]) return -1;
                else return 1;
            }
        });
        //从尾部找，按照尾部的大小顺序来找；用头部来包含
        for(int i = 0;i < points.length;i++){
            res++;
            int temp = points[i][1];//取到尾部大小
            //头部比较
            while(i < points.length && points[i][0] <= temp){
                i++;
            }
            //for中还有一个i++,这里要 --
            i--;
        }
        return res;
    }
}