452. Minimum Number of Arrows to Burst Balloons

If you cannot pass [[-2147483646,-2147483645],[2147483646,2147483647]]

use a[b] - b[0], maybe overflow,

so use Integer.compare(a[0], b[0])

Apparently a new test case has been added recently. If you cannot pass this one, then it is because the result of subtraction is too large and thus the overflow is encountered. So don't use a-b to compare when sorting. Use Integer.compare(a,b) instead!!!

greedy

time: O(nlogn)

space: O(1)

class Solution {
    public int findMinArrowShots(int[][] points) {
        // use a[b] - b[0], maybe overflow, so use Integer.compare(a[0], b[0])
        Arrays.sort(points, (a, b) -> Integer.compare(a[0],b[0])); 
        
        int res = 1;
        int end = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > end) {
                res++;
                end = points[i][1];
            } else {
                end = Math.min(end, points[i][1]);
            }
        }
        return res;
    }
}

/*
[[10,16],[2,8],[1,6],[7,12]]

              [10       16]
 [2.      8]
[1.  6]
        [7       12]
*/