Sharing my accepted greedy, Java solution


  • 0
    L

    All the recent interval based problems have been great, here's my solution to this one:

    public class Solution {
        /*
            ex:
            [[1,4],[3,5],[3,10],[4,6],[5,8]]
        
            ....
              ...
              ........
               ...
                ...
            
            Sort balloons by starting point. 
            As we move through the balloons we need to keep track of the min end point of current cluster. 
                once the current balloon has gone past the min end of previous cluster, it's time to fire an arrow. 
                
            (In the above example, once we get to the [5,8] balloon, 5 will be greater than 4, the "min end" of previous cluster)
                
            The question is.. is there ever a situation where bursting a big balloon early hurts my min number calculation.. 
            I think the answer is no because if two balloons don't overlap, a balloon which straddles them both does 
            not really minimize the number of arrows that have to be fired. 
        */
        
        public int findMinArrowShots(int[][] points) {
            if (points.length == 0){
                return 0;
            }
            sortByStartingPointAsc(points);
            int lastArrowFiredAt = 0;
            int arrowsFired = 0;
            int prevMinEndPoint = points[0][1];
            for (int i = 1; i < points.length; i++){
                int currentStartPoint = points[i][0];
                int currentEndPoint = points[i][1];
                if (currentStartPoint > prevMinEndPoint){
                    arrowsFired++;
                    lastArrowFiredAt = prevMinEndPoint;
                    prevMinEndPoint = currentEndPoint;
                } else {
                    prevMinEndPoint = Math.min(prevMinEndPoint, currentEndPoint);
                }
            }
            // check if last arrow was fired to burst a previous cluster
            if (lastArrowFiredAt < prevMinEndPoint){
                arrowsFired++;
            }
            return arrowsFired;
        }
        
        private void sortByStartingPointAsc(int[][] points){
            Arrays.sort(points, new Comparator<int[]>(){
                @Override
                public int compare(int[] e1, int[] e2){
                    return Integer.compare(e1[0], e2[0]);
                }
            });
        }
    }
    

Log in to reply
 

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