写太复杂了。

思想：确定带插入区间的每一个边界位于给定区间中的哪个位置，共同拥有5种情况

-1 |(0)_1_(2)|  (3)

当中。0,1,2这三种情况是一样的。

确定每一个带插入区间的两个边界分别属于哪种情况，记为flag0和flag1。

然后依据flag0和flag1的组合情况，分9种情况进行讨论

class Solution {

public:

    vector<Interval> insert(vector<Interval> &its, Interval ni) {

        int i,n=its.size(),j,k;

        int flag0=-1,flag1=-1;

        vector<Interval>ans;

        if(n==0){

            ans.push_back(ni);

            return ans;

        }

        for(i=0;i<n;++i)

			if((i==0||its[i-1].end<ni.start)&&its[i].start>ni.end)

				break;

        if(i<n||(i==n&&its[n-1].end<ni.start)){

            for(k=0;k<i;++k)ans.push_back(its[k]);

            ans.push_back(ni);

            for(;k<n;++k)ans.push_back(its[k]);

            return ans;

        }

        for(i=0;i<n;++i){

			if(its[i].end==ni.start){flag0=2;break;}

			else if(its[i].start==ni.start){flag0=0;break;}

            else if(its[i].start>ni.start)break;

            else if(its[i].start<ni.start&&its[i].end>ni.start){flag0=1;break;}

        }

        if(i==n&&flag0==-1)flag0=3;//no exist

        for(j=i;j<n;++j){

			if(its[j].end==ni.end){flag1=2;break;}

			else if(its[j].start==ni.end){flag1=0;break;}

            else if(its[j].start>ni.end)break;

            else if(its[j].start<ni.end&&its[j].end>ni.end){flag1=1;break;}

        }

        if(j==n&&flag1==-1)flag1=3;//可能存在

        for(k=0;k<i;++k)ans.push_back(its[k]);

        if(flag1==-1){

            if(flag0==3){

                ans.push_back(ni);

                return ans;

            }

            else if(flag0>=0&&flag0<=2){

                its[i].end=ni.end;

            }

            else if(flag0==-1){

                its[i].end=ni.end;its[i].start=ni.start;

            }

			ans.push_back(its[i]);

            for(k=j;k<n;++k)ans.push_back(its[k]);

        }

        else if(flag1>=0&&flag1<=2){

            if(flag0==3){

                its[j].start=ni.start;

            }

            else if(flag0>=0&&flag0<=2){

                if(i!=j){

                    its[i].end=its[j].end;

                    ans.push_back(its[i]);

                    for(k=j+1;k<n;++k)ans.push_back(its[k]);

                    return ans;

                }

            }

            else if(flag0==-1){

                if(i==j){

                    its[j].start=ni.start;

                }

                else{

                    its[i].start=ni.start;

                    its[i].end=its[j].end;

                    ans.push_back(its[i]);

                    for(k=j+1;k<n;++k)ans.push_back(its[k]);

                    return ans;

                }

            }

            for(k=i;k<n;++k)ans.push_back(its[k]);

        }

        else if(flag1==3){//j==n

            if(flag0==3){

                ans.push_back(Interval(-1117,-1117));//不存在

            }

            else if(flag0>=0&&flag0<=2){

                its[i].end=ni.end;

				ans.push_back(its[i]);

				return ans;

            }

            else if(flag0==-1){

                its[i].start=ni.start;

                its[i].end=ni.end;

				ans.push_back(its[i]);return ans;

            }

            for(k=i;k<n;++k)ans.push_back(its[k]);

        }

        return ans;

    }

};

这题C++假设採用从原vector删除元素的方法，因为存在大量的移动。会导致超时。

法2：

class Solution {

public:

    vector<Interval> insert(vector<Interval> &its, Interval ni) {

        int i,n=its.size(),j,k;

        if(n==0){

            its.push_back(ni);

            return its;

        }

		vector<Interval>ans;//分成三段

		for(i=0;i<n&&its[i].end<ni.start;++i)ans.push_back(its[i]);

		if(i<n){

			ni.start=min(its[i].start,ni.start);

		}

		else{

			ans.push_back(ni);

			return ans;

		}

		for(;i<n&&ni.end>=its[i].start;++i){

			ni.end=max(its[i].end,ni.end);

		}

		ans.push_back(ni);

		for(;i<n;++i)ans.push_back(its[i]);

		return ans;

    }

};