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

 1 /** 2  * Definition for an interval. 3  * struct Interval { 4  *     int start; 5  *     int end; 6  *     Interval() : start(0), end(0) {} 7  *     Interval(int s, int e) : start(s), end(e) {} 8  * }; 9  */10 class Solution {11 public:12     vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {13        14         int n=intervals.size();15         vector<Interval> result;16        17         if(n==0)18         {19             result.push_back(newInterval);20             return result;21         }22        23         int start=newInterval.start;24         int end=newInterval.end;25  26        27         bool isfindStart=false;28         bool isfindEnd=false;29         bool addCur=true;30        31         for(int i=0;i<n;i++)32         {33             addCur=true;34            35             if(!isfindStart)36             {37                 //和当前区间没有交叉,且在start的前面38                 if(start>intervals[i].end)39                 {40                     //需要添加当前元素41                     addCur=true;42                     //当前元素为最后一个元素时，则认为start找到了43                     if(i==n-1)  isfindStart=true;44                 }45                 else46                 {47                     //和当前区间有交叉 或者start小于当前区间48                    49                     start=min(start,intervals[i].start);50                     //后续就不用再找start了51                     isfindStart=true;52                    53                     //如果start和end没有和其他Interval有交叉54                     if(end<intervals[i].start) addCur=true;55                     else addCur=false;56                 }57             }58            59            60             if(!isfindEnd)61             {62                 //需要继续找end63                 if(end>intervals[i].end)64                 {65                    66                     if(start<=intervals[i].end) addCur=false;67  68                     if(i==n-1)69                     {70                         isfindEnd=true;71                        72                         if(addCur) result.push_back(intervals[i]);73                         result.push_back(Interval(start,end));74                        75                         continue;76                     }77                 }78                 else79                 {80                     //end小于当前区间，此时找到了end81                     end=end>=intervals[i].start?intervals[i].end:end;82  83                     //找到了end84                     isfindEnd=true;85                     if(end>=intervals[i].start) addCur=false;86                    87                     result.push_back(Interval(start,end));88                     if(addCur) result.push_back(intervals[i]);89                    90                     continue;91                 }92             }93            94             if(addCur) result.push_back(intervals[i]);95         }96         return result;97     }98 };