Simple Java Greedy Solution relatable to Interval Scheduling Concept


  • 0
    V

    A greedy solution using the idea of interval scheduling concept, we pick the balloons which finishes first on x axis and keep checking how many it covers and increase arrow count accordingly. Greedy stays ahead can be used to prove correctness and optimality.

    import java.util.Comparator;
    import java.util.Arrays;
    public class Solution {
        
        public int findMinArrowShots(int[][] points) {
            if(points == null || points.length == 0 || points[0].length == 0)
            return 0;
            
            // sort by finishing time way we do in task scheduling
            Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] int1, int[] int2) {
            Integer numOfKeys1 = int1[1];
            Integer numOfKeys2 = int2[1];
            return numOfKeys1.compareTo(numOfKeys2);
        }
    });
    
    int arrows = 1;
    int value = points[0][1];
    // continue for the one which are already covered
            for(int i=1;i<points.length;i++)
            {
                if(points[i][0]<=value && points[i][1]>=value)
                continue;
                else
                {
                    value=points[i][1];
                      arrows++;
                }
            }
            return arrows;
        }
    }
    

Log in to reply
 

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