2022.04.21(LC_452_用最少数量的箭引爆气球)

 方法：贪心

class Solution {
    public int findMinArrowShots(int[][] points) {
        //对[[-2147483646,-2147483645],[2147483646,2147483647]]来说
        //用Arrays.sort(points, (o1, o2) -> o1[1] - o2[1]);进行排序，相减会溢出
        //应该按以下写法对Xend升序排列
        Arrays.sort(points, (o1, o2) -> Integer.compare(o1[1], o2[1]));
        int ans = 0;
        int i = 0;
        while (i < points.length) {
            //当前气球的Xend坐标
            int end = points[i][1];
            int j = i + 1;
            //如果下一个气球的Xstart坐标小于等于上一个气球的Xend
            //说明它们可以被同一支箭引爆
            for ( ; j < points.length; j++) {
                int next = points[j][0];
                if (next > end) break;
            }
            ans++;
            i = j;
        }
        return ans;
    }
}

class Solution {
    public int findMinArrowShots(int[][] points) {
        //对[[-2147483646,-2147483645],[2147483646,2147483647]]来说
        //用Arrays.sort(points, (o1, o2) -> o1[1] - o2[1]);进行排序，相减会溢出
        //应该按以下写法对Xend升序排列
        Arrays.sort(points, (o1, o2) -> Integer.compare(o1[1], o2[1]));
        int ans = 1;
        //排序后右边界位置最靠左的气球
        int pos = points[0][1];
        for (int[] balloon : points) {
            //找到第一个不能被上一支箭引爆的气球
            if (balloon[0] > pos) {
                ans++;
                //更新右边界位置最靠左的气球的位置
                pos = balloon[1];
            }
        }
        return ans;
    }
}