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:
         result.add(interval);
         insertPos++;
    
    2) If no overlap - newInterval precedes the current interval:
        result.add(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
    			res.add(cur);
    			insertPos++;
    		} else if (cur.start > newInterval.end)   {// No Overlapping:  After newInterval
    			res.add(cur);
    		} 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.