题解 | #插入区间#
插入区间
http://www.nowcoder.com/practice/1d784b5472ab4dde88ea2331d16ee909
描述
给定一个无重叠的，按照区间起点升序排列的区间列表，在列表中插入一个新区间，如果有原区间有重合，则合并，请返回插入后的区间列表。
数据范围：区间列表长度满足 
， 区间的左右端点满足 
问题分析：插入区间，无非就是对要插入的区间对原区间列表两两比较。可以分如下几种情况。
假设原区间第一区间为[a0,b0]，最后一个区间为[an,bn]，需要新插入的区间为[e,f]。
一、e>=bn，当是大于时，直接在最后插入，当取=时，直接修改bn；
二、e>=an，直接让bn=max(bn,f)；
三、f<=a0，当是大于时，直接在前面插入，到取=时，直接修改a0；
四、f>=bn，当e<=a0时，直接清空原区间列表，插入new，否则循环找到第一个ai<e的位置，修改bi，然后删除i后面的所有。
以上是特殊情况。
而一般情况是：假设找到一个位置[a,b]，这个位置是最后一个ai<e的，而这个位置下一个位置是[c,d]，我们可以知道a<e<c；
那么此时的操作如下所示：
1、b>=f，直接无视，退出。2、b<e，分三种情况：f>c,f=c,f<c；3、b>=e，分三种情况：f>c,f=c,f<c。
一般情形就以上7种，具体每种情况应该怎么做看下面代码，有详细注释。
复杂度分析:
时间复杂度O(n)：最坏情况需要遍历整个列表。
空间复杂度O(1)：只定义了两个迭代器，从头到位没有其他变量，也没有申请额外的空间。
那么还有没有其他做法呢，肯定是有的，完全可以直接先插入进去，然后通过start来排序，直接调用sort(begin(),end(),cmp)。
cmp自己写根据start大小排序。然后逐个检查每个区间。是否符合要求，修改区间列表。这里就不写了，之前好像写过一个类似的，所以这次
换一个通过逻辑整理出来的算法。
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param Intervals Interval类vector
* @param newInterval Interval类
* @return Interval类vector
*/
vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
// write code here
if(Intervals.empty()) {
Intervals.push_back(newInterval);
return Intervals;
}
//第一个左比new右大，直接在第一个前插入new
if((Intervals.begin())->start>=newInterval.end) {
if((Intervals.begin())->start>newInterval.end) Intervals.insert(Intervals.begin(),newInterval);
else (Intervals.begin())->start=newInterval.start;
return Intervals;
}
if((Intervals.end()-1)->end<=newInterval.start) {
if((Intervals.end()-1)->end<newInterval.start)
Intervals.push_back(newInterval);//最后一个右比new左小，直接在最后插入
else (Intervals.end()-1)->end=newInterval.end;//最后一个右==new左，直接修改最后一个的右
return Intervals;
}
//最后一个的左<=new左，直接让最后一个的右=max(最后一个的右,new右)
if((Intervals.end()-1)->start<=newInterval.start) {
(Intervals.end()-1)->end=max((Intervals.end()-1)->end,newInterval.end);
return Intervals;
}
//最后一个的右<=new的右
if(newInterval.end>=(Intervals.end()-1)->end) {
if(newInterval.start<=(Intervals.begin())->start) {
Intervals.clear();
Intervals.push_back(newInterval);
}//如果第一个的左比new左大，直接清空原区间，插入new。
else {
vector<Interval>::iterator it=Intervals.end()-1;
while((*it).start>newInterval.start) --it;
(*it).end=newInterval.end;
Intervals.erase(it,Intervals.end());
}//从后往前循环找到第一个左比new左小的，然后让这个的右=new的右，后面的直接删掉
return Intervals;
}
vector<Interval>::iterator it=Intervals.begin();//it指向最后一个左比new左小的位置
while((*(it+1)).start<newInterval.start) ++it;//循环找到最后一个左比new左小的位置
if((*it).end>=newInterval.end) return Intervals;//1、如果it右比new右大，直接返回
vector<Interval>::iterator it2=it+1;
//b<e分三种情况（f>c,f=c,f<c）
if((*it).end<newInterval.start) {
if((*(it2)).start<newInterval.end) {//2.b<e,f>c
while((*it2).end<newInterval.end) it2=Intervals.erase(it2);
if(newInterval.end>=(*it2).start) (*it2).start=newInterval.start;
else Intervals.insert(it2,newInterval);
}
else if((*(it2)).start==newInterval.end) {//3、b<e,f=c
(*it2).start=newInterval.start;
}
else {//4、b<e,f<c
Intervals.insert(it+1,newInterval);
}
}
//b>=e,分三种情况(f<c,f=c,f>c)
else {
if((*(it2)).start<newInterval.end) {//5、b>=e,f>c
while((*it2).end<newInterval.end) it2=Intervals.erase(it2);
if(newInterval.end>=(*it2).start) (*it).end=(*it2).end,Intervals.erase(it2);
else (*it).end=newInterval.end;
}
else if((*(it2)).start==newInterval.end) {//6、b>=e,f=c
(*it).end=(*it2).end;
Intervals.erase(it2);
}
else {//7、b>=e,f<c
(*it).end=newInterval.end;
}
}
return Intervals;
}
};
