有些hard在于算法难，思路难想；有些hard在于corner case多，这题就是后者。

这题跟56. Merge Intervals是类似的，而且这个是已经排好了顺序给你；但是难度并没有下降，我觉得这种题目就是把所有可能的case都cover到就能AC了，但是往往可能你在纸上画都不一定能画得全，这可能也就是hard的原因（我在纸上画了）。这次我试了一下，一共调试了5次，start和end用max/min比较分别占了一次。这种题我感觉看答案只会被牵着鼻子走，自己要覆盖到所有的corner case才行。另外，一道题如果耗时太长脑力必然会严重下降。所以尽量速战速决。

public List
    
      insert(List
     
       intervals, Interval newInterval) {		List
      
        res = new ArrayList<>();		//corner case1		if (intervals.isEmpty()) {			res.add(newInterval);			return res;		}		while (!intervals.isEmpty()) {			if (intervals.get(0).start < newInterval.start && intervals.get(0).end < newInterval.start) {				res.add(intervals.remove(0));			} else {				break;			}		}		if (intervals.isEmpty()) {			res.add(newInterval);			return res;		}		//这里开始的intervals list第一个元素的end一定比newInterval的start大		//1. won't overlapping		if (intervals.get(0).start > newInterval.end) {			res.add(newInterval);			res.addAll(intervals);			return res;		}		//2. wrapped by the 1st interval		if (intervals.get(0).start <= newInterval.start && intervals.get(0).end >= newInterval.end) {			res.addAll(intervals);			return res;		}		//3. overlapping		Interval head = intervals.get(0);		if (head == null) return res;		int start = Math.min(head.start, newInterval.start);		int end;		while (newInterval.end >= head.end && intervals.size() > 1) {			intervals.remove(0);			head = intervals.get(0);		}		if (newInterval.end < intervals.get(0).start) {			end = newInterval.end;			res.add(new Interval(start, end));			res.addAll(intervals);			return res;		}		if (newInterval.end >= intervals.get(0).start) {			end = Math.max(intervals.remove(0).end, newInterval.end);			res.add(new Interval(start, end));			res.addAll(intervals);			return res;		}		// should have covered all possible cases		return null;	}复制代码