Greedy Algorithm Java O(n) with clear explain

  • 0

    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: - 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[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;

Log in to reply

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