Java Greedy Soution


  • 22
    public int findMinArrowShots(int[][] points) {
    	if(points==null || points.length==0 || points[0].length==0) return 0;
    	Arrays.sort(points, new Comparator<int[]>() {
    		public int compare(int[] a, int[] b) {
    			if(a[0]==b[0]) return a[1]-b[1];
    			else return a[0]-b[0];
    		}
    	});
    	
    	int minArrows = 1;
    	int arrowLimit = points[0][1];
    	for(int i=1;i<points.length;i++) {
    		int[] baloon = points[i];
    		if(baloon[0]<=arrowLimit) {
    			arrowLimit=Math.min(arrowLimit, baloon[1]);
    		} else {
    			minArrows++;
    			arrowLimit=baloon[1];
    		}
    	}
    	return minArrows;
    }
    

  • 0
    C

    Hi, I don't understand why you have to sort by the end?


  • 1
    C

    @CBK He is actually sorting by start in ascending order, note that if(a[0]==b[0]) return a[1]-b[1]; means only when starts of a and b are equal we then look at ends.


  • 0
    W

    I understand how your code runs, but I could not understand why it is correct. Could you please explain it?
    I know this is a linear search, which is trying to find one interval partially overlapped by as many other "balloon"s as possible, during the search the interval's span is non-increasing.
    Then moved to a new balloon, starting one new search.


  • -1
    public class Solution {
        public int findMinArrowShots(int[][] points) {
            if(points == null || points.length < 1){
                return 0;
            }
            int sum = points.length;
            Arrays.sort(points, (a,b)->{if(a[0] == b[0]) return a[1] - b[1];
                                         else return a[0] - b[0];});
            int count = 1;
            int start = points[0][1];
            for(int i = 1; i < points.length; i++){
                if(points[i][0] <= start){
                   sum--;
                    start = Math.min(start, points[i][1]);
                }else{
                    start = points[i][1];
                }
            }
            return sum;
        }
    }
    ``

  • 12
    H
     public int findMinArrowShots(int[][] points) {
            if(points==null || points.length==0) return 0;
         // sort points based on their end point. 
            Arrays.sort(points, new Comparator<int[]>(){
                public int compare(int[] p1, int[] p2)
                {
                    return Integer.compare(p1[1],p2[1]);
                }
            });
            int currentEnd = points[0][1];
            int count = 1;
            for(int[] p: points)
            {
            // if the point starts after currentEnd, it means this balloons not been bursted. Then we shot the balloon in its end point. Otherwise, means this balloon has been bursted, then ignore it.
                if(p[0]>currentEnd) {        
                    count++;
                    currentEnd = p[1];
                }
                else continue;
            }
            return count;
        }
    

  • 0
    H

    I think you could simplify the comparator by:

      Arrays.sort(points,(a,b) -> a[0]==b[0]? a[1]-b[1] : a[0]-b[0]);
    

    Just looks nicer maybe.


  • 1
    F

    @wsliubw From an easy to understand point of view, this greedy algorithm works because : 1, when sorted by end value, you will always need a shot for the first balloon(at its end) because if it's a stand alone balloon you obviously have to otherwise it has other balloons overlapping, in which case you also have to use an arrow at its end otherwise you will miss this balloon. 2, If you have overlapping balloon, it's good, your arrow will destroy them, and this way, you are creating a sub-problem, which start with a new set of balloons with these characteristics. You keep doing until no balloon is left.


  • 3
    F

    @CBK
    You don't need to actually sort by end. It's sufficient to sort by the start.
    This line arrowLimit=Math.min(arrowLimit, baloon[1]); always picks the least end limit that will cover the maximum number of balloons. Even if a higher limit is selected in previous iteration, it will ultimately narrow it down in future iterations.
    Example : [[2,6],[5,6],[2,4]] --> Suppose gets sorted as [[2,6],[2,4],[5,6]], it will still give the answer as 2.
    This works because before you move on to a new higher start value(here 5), you would have the least end value as "arrowLimit" from previous set of similar start value balloons (here 2,6 and 2,4 pairs)
    P.S I have tried without sorting the ends and my solution got accepted.


  • 3

    Typical greed algorithm. The question is equivalent to ask - maximally, how many non-overlapping balloons we can find? Each non-overlapping balloon will take 1 arrow to burst.

    Similar problems -

    1. Activity Selection Problem
    2. Non-overlapping Intervals
        public int findMinArrowShots(int[][] points) {
            int n = points.length; 
            if (n <= 1) return n; 
            
            PriorityQueue<int[]> pq = new PriorityQueue<>((p1, p2) -> p1[1] - p2[1]); 
            
            for (int i = 0; i < n; i++)
                pq.offer(points[i]); 
            
            int cnt = 1, end = pq.poll()[1]; 
            for (int i = 1; i < n; i++) {
                int[] cur = pq.poll();
                if (cur[0] > end) {
                    cnt++;
                    end = cur[1]; 
                }
            }
            return cnt; 
        }

  • 0
    L

    @HuanYe your solution is easy to understand


  • 3

    Basically the idea is to sort by end points. This is because, the end point decides how many balloons intersect, when you start moving towards right.

    If there is no intersection with the next balloon, then this balloon needs an arrow to be burst. And if there is an intersection, we need to find how many balloons can intersect so that we can burst all balloons with one arrow.

    public int findMinArrowShots(int[][] points) {
        if(points == null || points.length == 0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[1] - b[1]; // sort based on end points
            }    
        });
        
        int min = points[0][1], arrowCount = 1;
        for(int i = 1; i < points.length; i++) {
            // if does not intersect, need one more arrow for next set of balloons
            if(points[i][0] > min) { 
                arrowCount++;
                min = points[i][1];
            }
        }
        return arrowCount;
    }

  • 0

    Greedy solution:
    Sort by start time.
    Remove leftmost interval.
    If there is any other interval start before end of leftmost interval, this can be remove together, and set the end to be min ending value of those two intervals.
    So next time, if a interval starts before this end, it can be removed in same round too. Repeat the last step.

    If the next interval starts after the end, means we need a new arrow. repeat the previous steps.

        public int findMinArrowShots(int[][] points) {
          if(points.length == 0) return 0;    
          Arrays.sort(points, (a, b) ->{
              if(a[0] == b[0]) return a[1] - b[1];
              else return a[0] - b[0];
              });    
              
          int leftMostEnd = points[0][1];
          int count = 1;
          for(int i = 1; i < points.length; i++){
            if(points[i][0] <= leftMost){
              leftMostEnd = Math.min(points[i][1], leftMostEnd );   
            } else {
              count++; 
              leftMostEnd = points[i][1];
            }  
          }
          
          return count;
        }

  • 0

    @zzhai Hello, I am a little confused about the equivalent saying" how many non-overlapping balloons we can find". In this case, even we get the maximal non-overlapping balloons, we still need some extra arrows. Eg.
    |---------b1---||----b2---------||-----b3---||------b4-----|
    |-b5--||--b6-| |--b7-||-b8-|
    so that we need 6 arrows rather than 4
    b1 to b8 are the ballons


  • 0
    public int findMinArrowShots(int[][] points) {
            Arrays.sort(points, (o1, o2) -> o1 [0] - o2 [0] == 0 ? o1 [1] - o2 [1] : o1 [0] - o2 [0]);
            int idx = 0, res = 0;
            while (idx < points.length) {
                int end = points [idx][1];
                while (idx + 1 < points.length) { 
                	if (end >= points [idx + 1][0]) { end = Math.min(end, points [idx + 1][1]); idx ++; }
                	else break;
                }
                res ++; idx ++;
            }
            return res;
    }
    

  • 0
    F

    Hi, I noticed that if we use Arrays.sort() in java 8 format, then the code will much slower than the old format. I run each format twice, the time of java 8 format is 113ms, 126m, however, another one is 45 ms, 45ms. Can anyone explain why? Thanks!


Log in to reply
 

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