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;
}
Java Greedy Soution


@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.

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 nonincreasing.
Then moved to a new balloon, starting one new search.

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; } } ``

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; }

@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 subproblem, which start with a new set of balloons with these characteristics. You keep doing until no balloon is left.

@CBK
You don't need to actually sort by end. It's sufficient to sort by the start.
This linearrowLimit=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.

Typical greed algorithm. The question is equivalent to ask  maximally, how many nonoverlapping balloons we can find? Each nonoverlapping balloon will take 1 arrow to burst.
Similar problems 
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; }


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; }

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; }

@zzhai Hello, I am a little confused about the equivalent saying" how many nonoverlapping balloons we can find". In this case, even we get the maximal nonoverlapping balloons, we still need some extra arrows. Eg.
b1b2b3b4
b5b6 b7b8
so that we need 6 arrows rather than 4
b1 to b8 are the ballons

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; }