Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

题意是给出一组按起始升序排列的没有重合的区间，如果插入一个新区间，返回还是按照起始位置升序的合并后的区间。这道题和之前56题很像，并且用56题的解法也是完全可行的，只需要把新区间加入到list中，然后重新排序，之后的处理和56题一样，因为需要一次sort排序所以时间复杂度是O(nlogn)。

public List<Interval> insert1(List<Interval> intervals, Interval newInterval) {
    List<Interval> res = new ArrayList<>();
    if ((intervals == null || intervals.size() == 0) && newInterval == null) {
        return res;
    }

    intervals.add(newInterval);
    Collections.sort(intervals, new Comparator<Interval>() {
        public int compare(Interval i1, Interval i2) {
            return i1.start - i2.start;
        }
    });

    int left = Integer.MIN_VALUE, right = Integer.MIN_VALUE;
    for (Interval val : intervals) {
        if (val.start > right) {
            if (right != Integer.MIN_VALUE) {
                res.add(new Interval(left, right));
            }
            left = val.start;
            right = val.end;
        } else if (val.end > right) {
            right = val.end;
        }
    }
    res.add(new Interval(left, right));

    return res;
}

这样的解法虽然过了，但是总感觉不是这道题目的本意，翻看discuss后，发现还真是，有一种解法很好的利用了已知区间的特性。这个解法的思路是：分析插入空间和已知空间的关系。1、已知区间的end小于插入区间的start，这种情况没有重合，可以直接把这个区间加入到结果中；2、已知区间end大于等于newInterval的start，并且start小于等于newInterval的end，此时发生重合，需要维护重合区间的start和end，最后把这个重合区间加入结果中；3、剩余区间的start就大于newInterval的end，这部分可以直接加入结果。整个过程是线性的，所以时间复杂度是O(n)。

public List<Interval> insert2(List<Interval> intervals, Interval newInterval) {
    List<Interval> res = new ArrayList<>();
    if ((intervals == null || intervals.size() == 0) && newInterval == null) {
        return res;
    }

    int i = 0;
    int n = intervals.size();
    while (i < n && intervals.get(i).end < newInterval.start) {
        res.add(intervals.get(i++));
    }

    int mergeLeft = newInterval.start;
    int mergeRight = newInterval.end;
    while (i < n && intervals.get(i).start <= newInterval.end) {
        mergeLeft = Math.min(intervals.get(i).start, newInterval.start);
        mergeRight = Math.min(intervals.get(i).end, newInterval.end);
        i++;
    }
    res.add(new Interval(mergeLeft, mergeRight));

    while (i < n) {
        res.add(intervals.get(i));
    }

    return res;
}