Min number of Arrows - Java Solution, simple greedy


  • 0
    V
    public class Solution {
        public int findMinArrowShots(int[][] points) {
            int n = points.length;
            if( n == 0 ) return 0;
            /* sort by ending dia */
            Arrays.sort(points, new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    if(a[0] == b[0])    return a[1]-b[1];
                    else return a[0]-b[0];
                }
            });
            
            int i = 0, minArrows = 0, end = points[0][1]; 
            while(true) {
                /* update minimum ending dia for buring the current set of balloons */
                while( i<n && points[i][0] <= end )     
                    end = Math.min(end, points[i++][1]);
                minArrows += 1;
                /* Update ending dia for the next set of balloons */
                if(i < n ) end = points[i][1];
                else break; /* we are done */
            }
            return cnt;
        }
    }
    

    Open to suggestions and improvisations.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.