[LeetCode] 452. Minimum Number of Arrows to Burst Balloons

 Problem : https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

Sort the balloons by coordination first. Then combine the sections as much as possible.

class Solution {
    public int findMinArrowShots(int[][] points) {
        // sort points by its x coordination
        Arrays.sort(points, (a, b) -> {
            // don't use a[0] - b[0]. it may cause int overflow.
            if (a[0] != b[0]) {
                return a[0] < b[0] ? -1 : 1;
            }
            
            return a[1] < b[1] ? -1 : 1;
        });
        
        // assume every balloon needs one arrow
        int result = points.length;
        
        // start with the first ballon
        int right = points[0][1];
        
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] <= right) {
                // ith ballon can be bursted with the last balloon
                result -= 1;
                // update the right 
                right = Math.min(right, points[i][1]);
            } else {
                // start a new right
                right = points[i][1];
            }
        }
        
        return result;
    }
}