My Java Solution


  • 0
    _

    public class Solution {
    /*
    * Solution: 1.Sort intervals by start(1st) and end(2nd).
    * 2.Use Greedy strategy.
    * - if start1 == start2 then we remove start2 because it has
    * larger end which means the longest interval
    * - if end1 > start2 which means we have to remove one from two intervals, then we remove the
    * interval which has larger end because it may cross more start
    * - if end1 <= start2 then we don't need to remove anyone of them
    */

    public int eraseOverlapIntervals(Interval[] intervals) {
    	if (intervals == null || intervals.length < 2)
    		return 0;
    	Arrays.sort(intervals, new Comparator<Interval>() {
    
    		@Override
    		public int compare(Interval o1, Interval o2) {
    
    			return (Integer.compare(o1.start, o2.start) != 0) ? Integer.compare(o1.start, o2.start)
    					: Integer.compare(o1.end, o2.end);
    		}
    
    	});
    	Interval interval = intervals[0];
    	int count = 0;
    	for (int i = 1; i < intervals.length; i++) {
    		if (intervals[i].start == interval.start) {
    			count++;
    		} else if (intervals[i].start < interval.end) {
    			count++;
    			interval = (intervals[i].end < interval.end) ? intervals[i] : interval;
    		} else {
    			interval = intervals[i];
    		}
    	}
    	return count;
    }
    

    }


Log in to reply
 

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