JAVA O(N lgN) Greedy Solution, 24 lines


  • 0

    Just sort the array (end point as first preference, start point as second preference) and then use a greedy approach.

    public class Solution {
        public int eraseOverlapIntervals(Interval[] intervals) {
            int len = intervals.length;
            if(len <= 1) return 0;
            Arrays.sort(intervals, new Comparator<Interval>(){
               public int compare(Interval a, Interval b){
                   if(a.end == b.end){
                       return Integer.compare(a.start,b.start);
                   }else{
                       return Integer.compare(a.end,b.end);
                   }
               } 
            });
            
            int nonLap = 1;
            int curE = intervals[0].end;
            for(int i = 1; i < len; i++){
                if(curE <= intervals[i].start){
                    curE = intervals[i].end;
                    nonLap++;
                }
            }
            return len-nonLap;
        }
    }
    

Log in to reply
 

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