https://leetcode.com/problems/insert-interval

Given a set ofnon-overlappingintervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals[1,3],[6,9], insert and merge[2,5]in as[1,5],[6,9].

Example 2:
Given[1,2],[3,5],[6,7],[8,10],[12,16], insert and merge[4,9]in as[1,2],[3,10],[12,16].

This is because the new interval[4,9]overlaps with[3,5],[6,7],[8,10].

这个题就相当于merge interval。唯一区别就是当前的newInterval 还没有排序

我们其实只要把newInterval 插入到相应的位置（按照start 的大小) 之后就是一样的处理了

如果按照上面 的做法，需要两次遍历，1 for insert 1 for merge

其实我们可以在一次中做完这两步

1. 插入所有在 newInterval start之前的 intervals
2. 此时 intervals[i..n-1] 的 end 都比newInterval 大，需要处理是否需要merge
3. merge condition: interval[i].start >= newInterval.end

如图所示 红色是newInterval, 其余为每一个interval 可能与newInterval中的位置。

我们首先处理 黑色虚线左边的情况，之后处理虚线之间的， 最后处理右边的

=》 从图中可知，merge 的条件是 interval[i]的start 在newInterval的前面

这里我们就可以简单的把newInterval 插入到interval[i..n-1]的head 前，然后进行merge interval的遍历操作

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<Interval>();
        if (intervals == null || newInterval == null) {
            return result;
        }

        // add intervals with smaller end first
        int i = 0;
        int n = intervals.size();
        while (i < n && intervals.get(i).end < newInterval.start) {
            result.add(intervals.get(i));
            i++;
        }
        // merge intervals
        while (i < n) {
            if (newInterval.end >= intervals.get(i).start) {
                newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
                newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
            } else {
                result.add(newInterval);
                newInterval = intervals.get(i);
            }
            i++;
        }
        result.add(newInterval);
        return result;
    }