Hard

首先遍歷到newInterval可能跟現(xiàn)在list里的interval有交集的地方. 也就是至少得intervals.get(i).end >= newInterval.start的地方. 這樣子再先判斷intervals.get(i).start 是不是小于等于newInterval.end, 不然也沒交集. 然后我們簡單地求出一個這兩個交集里面 start最小，end最大的區(qū)域，按照這個新的start, end來new出新的newInterval， 把原來interval List里這個位置的元素刪除, 但不要急著現(xiàn)在就insert到intervals List當中，而是要繼續(xù)遍歷. 但是后面的遍歷要跟剛剛新new出來的newInterval有交集，同樣的按照相同的步驟更新interval List和newInterval. 遍歷到一個無交集的interval時，退出while循環(huán)，這時候再把現(xiàn)在的newInterval加到interval List的index = i的地方.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int i = 0;
        while (i < intervals.size() && intervals.get(i).end < newInterval.start){
            i++;
        }
        while (i < intervals.size() && intervals.get(i).start <= newInterval.end){
            newInterval = new Interval(Math.min(intervals.get(i).start, newInterval.start), 
                                       Math.max(intervals.get(i).end, newInterval.end));
            intervals.remove(i);
        }
        intervals.add(i, newInterval);
        return intervals;
    }
}