Ac solution code


  • 0

    The basic idea is sorting the intervals by its start. Then compare intervals[i]'s start with intervals[i-1]'s end, merge the overlapping intervals correspondingly. As the following:

    Time complexity= O(nlgn) for sorting + O(n) for merging = O(nlgn + n) = O(nlgn)

    public List<Interval> merge(List<Interval> intervals) {
    	List<Interval>res = new ArrayList<Interval>();
    	if (intervals == null || intervals.isEmpty()) return res;
    	
    	Collections.sort(intervals, new Comparator<Interval>(){
    		public int compare(Interval i1, Interval i2) {
    			return i1.start - i2.start;// Sort ascendingly by interval's start
    		}
    	});
    	
    	Interval last = intervals.get(0);
    	for (int i = 1; i < intervals.size(); i++) { 
    	    Interval cur = intervals.get(i);
    		if (cur.start <= last.end) {
    			last.end = Math.max(cur.end, last.end);
    		} else {
    			res.add(last);
    			last = cur; 
    		}
    	}
    	
    	res.add(last);// Add the last interval
    	return res;
    }

Log in to reply
 

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