Java Solution with O(1) space


  • 1
    Y
    public List<Interval> merge(List<Interval> intervals) {
    	if (intervals == null || intervals.size() < 2)
    		return intervals;
    	intervals.sort(new Comparator<Interval>() {
    		public int compare(Interval it1, Interval it2) {
    			return it1.start - it2.start;
    		}
    	});
    	int length = 1;
    	for(int i = 1; i < intervals.size(); i++) {
    		if(intervals.get(length - 1).end < intervals.get(i).start) {
    			intervals.set(length++ , intervals.get(i));
    		}else {
    			intervals.get(length - 1).end = Math.max(intervals.get(length - 1).end , intervals.get(i).end);
    		}
    	}
    	return intervals.subList(0, length);
    }
    

Log in to reply
 

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