Java - O(N logN) - Greedy - Well Explained


  • 0
    A

    We will do a Greedy solution.

    • First sort the intervals with start followed by end values.
    • Traverse the array, if there is an overlap(start of current is less than end of previous)
      Chose the one with smaller end time(being greedy).
      Example: [[1,17],[1,4],[4,10]]
      We should choose Math.min(4,17) to stay and remove [1,17] as removing the larger will give more scope
        public int eraseOverlapIntervals(Interval[] intervals) {
            if(intervals == null) return 0;
            Arrays.sort(intervals, (a,b) -> {
                int start = Integer.compare(a.start, b.start);
                if(start == 0) start = Integer.compare(a.end, b.end);
                return start;
            });
            
            int count = 0;
            for(int i = 1; i < intervals.length; i++){
                if(intervals[i].start < intervals[i-1].end){
                    //if start of current is less than end of previous, we will remove the one with larger end time
                    count++;
                    intervals[i].end = Math.min(intervals[i].end, intervals[i-1].end);
                }
            }
            return count;
        }
    

Log in to reply
 

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