Ac solution code

  • 0

    Compare newInterval with each interval in the original intervals, as the following:

    1) If no overlap - newInterval succeeds the current interval:
    2) If no overlap - newInterval precedes the current interval:
        insertPos doesn't change        
    3) If overlapped: 
        // merge newInterval with the old interval 
        newInterval.start = Math.min(newInterval.start, interval.start);
        newInterval.end = Math.max(newInterval.end, interval.end);
        insertPos doesn't change
    Finally, add newInterval to result array at insertPos.

    Time complexity = O(n)

    As each interval in the original intervals is only compared with newInterval once, so time complexity is O(n).

      public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    	List<Interval>res = new LinkedList<Interval>();
    	if (intervals == null) return res;
    	int insertPos = 0;
    	for (Interval cur : intervals) {
    		if (cur.end < newInterval.start)   {// No Overlapping: Before newInterval
    		} else if (cur.start > newInterval.end)   {// No Overlapping:  After newInterval
    		} else {// Overlapping
    			newInterval.start = Math.min(newInterval.start, cur.start);
    			newInterval.end = Math.max(newInterval.end, cur.end);    			
    	res.add(insertPos, newInterval);
        return res;

Log in to reply

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