Given a set of non-overlapping intervals, 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:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
Example 2:
Input: intervals =[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval =[4,8]Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval[4,8]overlaps with[3,5],[6,7],[8,10].
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
一个已经排好序的区间数组，现在要插入一个新的区间，并且如果能合并则需要合并。最简单的方法就是把新加入的区间和原有区间一起排个序，然后统一合并，问题就转换为LeetCode Merge Intervals了。
但是原有区间数组是已经按start排序了，所以有更简单的办法。我们可以分三个过程插入新的区间，首先把明显小于新区间的区间放到结果数组中，然后处理所有可能和新区间有overlap的区间，不断合并并更新新区间，直到无法再合并时，把新区间加入结果数组中，最后把明显大于新区间的区间放到结果数组中。
完整代码如下：
class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval)
{
vector<Interval> ans;
int i = 0, n = intervals.size();
while (i < n && intervals[i].end < newInterval.start)
ans.push_back(intervals[i++]);
while (i < n && newInterval.end >= intervals[i].start) {
newInterval.start = min(newInterval.start, intervals[i].start);
newInterval.end = max(newInterval.end, intervals[i].end);
++i;
}
ans.push_back(newInterval);
while (i < n)
ans.push_back(intervals[i++]);
return ans;
}
};本代码提交AC，用时13MS。