1.题目要求在一些现在区间vector中，插入一个新的区间，并更新整个区间集（如果发生交集）。
2.主要思路是遍历一遍（时间复杂度为O（n）），查询当前的区间是否能插入的区间发生合并，合并分为四种情况：相交有两种([2,5]和[4,6]一前一后相交，[4,6]和[2,5]一后一前相交)，包含有两种([1,7]和[4,6]包含，[4,6]和[1,7]被包含)。
3.如果发生合并，记录合并的位置，把之前没有收到影响的区间直接压入新集合，从合并的位置开始使用Merge Intervals的方法进行合并检测。
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:
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].
AC代码：
[c language=”++”]
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
static bool cmp(const Interval&a, const Interval&b)
{
return a.start < b.start;
}
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> result=intervals;
bool isMerge=false;
int changeIdx=-1;//记录被改变区间的位置
for(int i=0;i<result.size();i++)
{
if( (newInterval.start<=result[i].end && newInterval.start>=result[i].start )
||(newInterval.end>=result[i].start && newInterval.end<=result[i].end )
||(newInterval.start<=result[i].start && newInterval.end>=result[i].end )
||(newInterval.start>=result[i].start && newInterval.end<=result[i].end ))
{/*共分四种情况:
相交有两种([2,5]和[4,6]一前一后相交，[4,6]和[2,5]一后一前相交)
包含有两种([1,7]和[4,6]包含，[4,6]和[1,7]被包含)*/
isMerge=true;//进行了合并，标记
changeIdx=i;//记录被改变区间的位置
result[i].start=min(result[i].start,newInterval.start);
result[i].end=max(result[i].end,newInterval.end);
break;
}
}
if(!isMerge)
{//没有发生合并，证明新区间与现有的区间没有交集，直接压入并排序
result.push_back(newInterval);
sort(result.begin(), result.end(), cmp);
return result;
}
else
{//进行了合并
vector<Interval> result2(0);
for(int i=0;i<changeIdx;i++)
{//前面的区间没有受影响，直接压进去即可
result2.push_back(result[i]);
}
int start=result[changeIdx].start;
int cover=result[changeIdx].end;
for(int i=changeIdx+1;i<result.size();i++)
{//从受影响的区间开始考虑合并，如Merge Intervals的做法
if (result[i].start <= cover)
cover = max(cover, result[i].end);
else
{
result2.push_back(Interval(start, cover));
start = result[i].start;
cover = result[i].end;
}
}
//把最后的一个区间压进去
result2.push_back(Interval(start, cover));
return result2;
}
}
};
[/c]