# Greedy Algorithm Java O(n) with clear explain

• This problem is another version of finding largest non-overlapping interval set(or the course scheduling problem).

Just use the greedy algorithm.

Why is this problem equal to finding out the largest non-overlapping interval set? I will give a brief proof below

``````Let's assume there are N non overlapping balloon in the input, and we only give them M shot(M < N). According to the pigeon hole principle, there must be one balloon from the N that is not burst. Therefore, we need N shot.
``````

As for the proof for how to find out the largest non-overlapping algorithm, please take a look at this course note: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf - chapter 7.2 scheduling class

This is a very classic greedy algorithm.

``````public class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return Integer.compare(a[1], b[1]);
}
});

int end = Integer.MIN_VALUE;
int ans = 0;

for(int i = 0; i < points.length; i ++) {
if(i == 0 || points[i][0] > end) {
end = points[i][1];
ans ++;
}
}

return ans;
}
}
``````

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