本文共 1693 字，大约阅读时间需要 5 分钟。

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

既然有序了，就简单了。

class Solution {public:    vector
   
     insert(vector
    
      &intervals, Interval newInterval) {        int i = 0;        int len = intervals.size();        if(0 == len) { intervals.push_back(newInterval); return intervals;}        vector
     
       re;        //find the insert position of start.        while(i < len && intervals[i].end < newInterval.start){            re.push_back(intervals[i]);            ++i;        }        //at the right,         if(i == len){re.push_back(newInterval); return re; }        int j = i;        //find the insert position of end.        while(j < len && intervals[j].end < newInterval.end){            ++j;        }        Interval jion;        jion.start = min(intervals[i].start, newInterval.start);        if(j == len){            jion.end = newInterval.end;            re.push_back(jion);            return re;        }            if(newInterval.end < intervals[j].start){           --j;           jion.end = newInterval.end;           re.push_back(jion);        }         else{            jion.end = intervals[j].end;            re.push_back(jion);        }        ++j;        while(j < len){            re.push_back(intervals[j]);            ++j;        }        return re;    }};
     
    
   

转载地址：http://drlji.baihongyu.com/