Simple Solution


  • 5
    1. Order intervals by start point.
    2. Record the end of the last valid interval.
    3. For each interval, if is start point is >= the end of the last valid interval, increment the count of valid intervals, and move the end point to the end of the current interval. Otherwise just set the new end point to the minimum between the two overlapping intervals.
    4. Return the difference between the number of intervals in the input array and the number of valid intervals you found in the previous way.

    Here is my implementation:

    public int eraseOverlapIntervals(Interval[] intervals) {
    	if(intervals==null || intervals.length==0) return 0;
    	Arrays.sort(intervals, new Comparator<Interval>() {
    		public int compare(Interval i1, Interval i2) {
    			return i1.start-i2.start;
    		}
    	});
    	int count=1;
    	int lastEnd = intervals[0].end;
    	for(int i=1;i<intervals.length;i++) {
    		Interval currentInterval = intervals[i];
    		if(currentInterval.start>=lastEnd) {
    			count++;
    			lastEnd=currentInterval.end;
    		} else {
    			lastEnd=Math.min(currentInterval.end,lastEnd);
    		}
    	}
    	return intervals.length-count;
    }
    

Log in to reply
 

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