Given a non-overlapping interval list which is sorted by start point.
Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).
Example
Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].
Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].
思路
我们新建一个ArrayList，把输入中的Interval一个一个放进去，并且维护一个插入新Interval的位置。
最后把这个新要插入的Interval放进ArrayList。
遍历输入并插入时的逻辑是：
1 如果当前的Interval小于新的Interval，那么直接放进ArrayList。并且插入位置加1。
2 如果当前的Interval大于新的Interval，那么直接放进ArrayList。不需要更新插入位置。因为输入是有序的。所以肯定插入位置在前面。
3 如果当前的Interval和新的Interval有重叠。那么我们不把它加进ArrayList，而是合并这两个重叠的Interval成为新的Interval，并且进入下一次循环。
最后在已经把所有输入的Interval加完以后，把新的Interval插入我们更新结束的位置。
Code
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
class Solution {
/**
* Insert newInterval into intervals.
* @param intervals: Sorted interval list.
* @param newInterval: A new interval.
* @return: A new sorted interval list.
*/
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> result = new ArrayList<Interval>();
// write your code here
if (intervals == null || newInterval == null) {
return intervals;
}
int pos = 0;
for (Interval interval : intervals) {
if (interval.end < newInterval.start) {
result.add(interval);
pos++;
}
else if (interval.start > newInterval.end) {
result.add(interval);
}
else {
newInterval.start = Math.min(interval.start, newInterval.start);
newInterval.end = Math.max(interval.end, newInterval.end);
}
}
result.add(pos, newInterval);
return result;
}
}
