描述

给定一个无重叠的，按照区间起点升序排列的区间列表，在列表中插入一个新区间，如果有原区间有重合，则合并，请返回插入后的区间列表。
数据范围：区间列表长度满足  ， 区间的左右端点满足 
问题分析：插入区间，无非就是对要插入的区间对原区间列表两两比较。可以分如下几种情况。
假设原区间第一区间为[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;
    }
};