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

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

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> 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;
    }

FB8294243396263939A5431A80B6B0AF.jpg