Simple O(n) Java Solution (3ms)


  • 0
    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> res = new ArrayList<Interval>();
    		int len = intervals.size();
    		// binary search
    		boolean only_once = false;
    		Interval last = null, curr = null;
    		int i = 0;
    		while (i < len || !only_once) {
    			curr = i < len ? intervals.get(i) : newInterval;
    			if (!only_once && curr.start >= newInterval.start) {
    				only_once = true;
    				curr = newInterval;
    				i--;
    			}
    			if (res.size() == 0 || curr.start > last.end) {
    				res.add(curr);
    				last = curr;
    			}
    			else {
    				last.start = Math.min(last.start, curr.start);
    				last.end = Math.max(last.end, curr.end);
    			}
    			i ++;
    		}
    		return res;
        }
    }

Log in to reply
 

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