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<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
int i = 0;
int len = intervals.size();
if(0 == len) { intervals.push_back(newInterval); return intervals;}
vector<Interval> 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;
}
};