57. Insert Interval

Hard

首先遍历到newInterval可能跟现在list里的interval有交集的地方. 也就是至少得intervals.get(i).end >= newInterval.start的地方. 这样子再先判断intervals.get(i).start 是不是小于等于newInterval.end, 不然也没交集. 然后我们简单地求出一个这两个交集里面 start最小，end最大的区域，按照这个新的start, end来new出新的newInterval， 把原来interval List里这个位置的元素删除, 但不要急着现在就insert到intervals List当中，而是要继续遍历. 但是后面的遍历要跟刚刚新new出来的newInterval有交集，同样的按照相同的步骤更新interval List和newInterval. 遍历到一个无交集的interval时，退出while循环，这时候再把现在的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;
    }
}