首页 > 代码库 > [LeetCode] Insert Interval

[LeetCode] Insert Interval

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].

注意各种if与对应else if之间的排序及不能有互相包含的情况就OK!

class Solution {public:    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {        vector<Interval> result;        Interval temp;        int len = intervals.size();        if(len==0){ //特殊情况,intervals是空时直接可以得到结果            result.push_back(newInterval);            return result;        }                    int startIndex,endIndex;        int i,startflag=0,endflag=0;        for(i = 0;i<len;){            if(intervals[i].start<=newInterval.start && intervals[i].end >= newInterval.end){//新区间在某个区间内                return intervals;            }else if(startflag == 0 && intervals[i].start > newInterval.end ){//新区间在所有区间外,在某个区间之前                result.push_back(newInterval);                startflag = 1;                endflag = 1;                break;            }else if(intervals[i].end < newInterval.start && i!=len-1){//新区间的起点在此区间之后                result.push_back(intervals[i]);                i++;            }else if(startflag == 0 && newInterval.start < intervals[i].start &&                 newInterval.end >=  intervals[i].start && newInterval.end <= intervals[i].end){//新区间的起点在此区间之前,终点在此区间之间                startflag = 1;                endflag = 1;                temp.start  = newInterval.start;                temp.end    = intervals[i].end;                result.push_back(temp);                i++;                break;            }else if(startflag == 0 && newInterval.start < intervals[i].start &&                newInterval.end > intervals[i].end){ //新区间的起点在此区间之前,终点超出此区间                startflag = 1;                temp.start  = newInterval.start;                            }else if(startflag == 0 && newInterval.start >= intervals[i].start &&                newInterval.start <=  intervals[i].end && newInterval.end > intervals[i].end){//新区间的起点在此区间之间,终点超出此区间                startflag = 1;                temp.start  = intervals[i].start;                            }else if(startflag == 0  && i==len-1 && intervals[i].end< newInterval.start){//新区间在最后一个区间外                result.push_back(intervals[i]);                result.push_back(newInterval);                return result;                }            if(startflag==1 && endflag==0 && i==len-1 && newInterval.end >intervals[i].end){//新区间的终点在最后一个区间之后                temp.end = newInterval.end;                endflag = 1;                i++;                result.push_back(temp);                return result;                             }else if(startflag==1 && endflag==0 && newInterval.end > intervals[i].end){//新区间的终点越过此区间                i++;                continue;            }else if(startflag==1 && endflag==0 && newInterval.end < intervals[i].start){//新区间的终点在此区间之前               endflag = 1;               temp.end = newInterval.end;               result.push_back(temp);               break;            }else if(startflag==1 && endflag==0 && newInterval.end >= intervals[i].start &&                newInterval.end <= intervals[i].end){//新区间的终点在此区间之间                endflag = 1;                temp.end = intervals[i].end;                i++;                result.push_back(temp);                break;            }        }//end for                            while(i<len){           result.push_back(intervals[i++]);        }        return result;    }//end func};