# Insert Interval

## Question

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


## 题解

1. [N], [I] <==> newInterval.end < interval.start, 由于 intervals 中的间隔数组已经为升序排列，那么遍历到的下一个间隔的左边元素必然也大于新间隔的右边元素。
2. [NI] <==> newInterval.end == interval.start，这种情况下需要进行合并操作。
3. [IN] <==> newInterval.start == interval.end, 这种情况下也需要进行合并。
4. [I], [N] <==> newInterval.start > interval.end, 这意味着newInterval有可能在此处插入，也有可能在其后面的间隔插入。故遍历时需要在这种情况下做一些标记以确定最终插入位置。

### Java

/**
* 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>();
if (intervals == null || intervals.isEmpty()) {
if (newInterval != null) {
}
return result;
}

int insertPos = 0;
for (Interval interval : intervals) {
if (newInterval.end < interval.start) {
// case 1: [new], [old]
} else if (interval.end < newInterval.start) {
// case 2: [old], [new]
insertPos++;
} else {
// case 3, 4: [old, new] or [new, old]
newInterval.start = Math.min(newInterval.start, interval.start);
newInterval.end = Math.max(newInterval.end, interval.end);
}
}

return result;
}
}