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].

題意是給出一組按起始升序排列的沒有重合的區(qū)間爷肝，如果插入一個(gè)新區(qū)間滔灶，返回還是按照起始位置升序的合并后的區(qū)間桨吊。這道題和之前56題很像吗浩，并且用56題的解法也是完全可行的，只需要把新區(qū)間加入到list中，然后重新排序，之后的處理和56題一樣奴紧，因?yàn)樾枰淮蝧ort排序所以時(shí)間復(fù)雜度是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后跛十，發(fā)現(xiàn)還真是彤路，有一種解法很好的利用了已知區(qū)間的特性。這個(gè)解法的思路是：分析插入空間和已知空間的關(guān)系芥映。1洲尊、已知區(qū)間的end小于插入?yún)^(qū)間的start，這種情況沒有重合奈偏，可以直接把這個(gè)區(qū)間加入到結(jié)果中坞嘀；2、已知區(qū)間end大于等于newInterval的start惊来，并且start小于等于newInterval的end丽涩，此時(shí)發(fā)生重合，需要維護(hù)重合區(qū)間的start和end裁蚁，最后把這個(gè)重合區(qū)間加入結(jié)果中矢渊；3、剩余區(qū)間的start就大于newInterval的end厘擂，這部分可以直接加入結(jié)果昆淡。整個(gè)過程是線性的锰瘸，所以時(shí)間復(fù)雜度是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;
}