Greedy Java O(nlogn) with commented code.


  • 0
    K
    public class Solution {
        public int findMinArrowShots(int[][] points) {
            if(points.length == 0) return 0;
            //Sort according to x_start
            //If x_start_i == x_start_j then sort according to x_end
            Arrays.sort(points, new Comparator<int[]>(){
                public int compare(int[] p1, int[] p2)
                {
                    if(p1[0] == p2[0])
                    {
                        return p1[1] - p2[1];
                    }
                    return p1[0] - p2[0];
                }
            });
            int count = 0;
            //max point of current set of single arrow shootable balloons
            int curMax = points[0][1];
            //count number of single arrow shootable intervals
            for(int i = 1; i < points.length; ++i)
            {
                //If we can't shoot current balloon and previous set of baloons using single arrow
                if(curMax < points[i][0])
                {
                    curMax = points[i][1];
                    ++count;
                }
                else
                {
                    //If we can shoot current balloon and previous balloons with one arrow
                    //reset limit of x_end of overall interval
                    curMax = Math.min(curMax, points[i][1]);
                }
                
            }
            //Incerement here to account for last set balloons
            ++count;
            return count;
        }
    }
    

Log in to reply
 

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