452.Minimum Number of Arrows to Burst Balloons (Medium)

452.Minimum Number of Arrows to Burst Balloons (Medium)

我的个人网站
点击可查看所有文章

与435差不多 这题是重合的也要算上
但是有个坑点 下面这个测试数据
**注意：**因为我们在sort排序构造的Comparator中习惯性写 返回 a[1]-b[1] int会溢出

[[-2147483646,-2147483645],[2147483646,2147483647]]

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

1 <= points.length <= 104
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

public int findMinArrowShots(int[][] points) {
        int length = points.length;
        int n = length;
        if (0 == length) {
            return 0;
        }
        Arrays.sort(points, new Comparator() {
            public int compare(int[] a, int[] b) {
                return a[1] < b[1] ? -1 : 1;
            }
        });

        double prev = points[0][1];
        for (int i = 1; i < length; i++) {
            if (prev >= points[i][0]) {
                n--;
            } else {
                prev = points[i][1];
            }
        }
        return n;
    }