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;
}
}
