Simple Java Greedy Solution relatable to Interval Scheduling Concept

  • 0

    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)
            return arrows;

Log in to reply

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