Greedy Algorithm Java O(n) with clear explain


  • 0
    J

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

Log in to reply
 

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