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]
.
思路:
Insert Interval是Merge Intervals的一个延伸问题,先看看怎么Merge
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18]
,
return [1,6],[8,10],[15,18]
.
vector<Interval> merge(vector<Interval> &intervals) {
if(intervals.size() <= )
return intervals; vector<Interval> vres;
sort(intervals.begin(), intervals.end(), intvalcomp);//先对interval排序
Interval tmp(intervals[]);
for(Interval it:intervals){
if(tmp.start == it.start){
tmp.end = it.end;
}else if(tmp.end >= it.start){//intervals有序,必然有tmp.start < it->start
if(tmp.end < it.end)//直接无视后者{[1,4],[2,3]}
tmp.end = it.end;//直接吞并后者{[1,3],[2,4]}
}else{
vres.push_back(tmp);//不相交
tmp = it;
}
}
vres.push_back(tmp);//漏掉这句会fail{[1,4],[1,4]}
return vres;
} bool intvalcomp(Interval a, Interval b){
if(a.start == b.start)
return a.end < b.end;
else
return a.start < b.start;
}
现在有了这个Merge好了的不相交区间序列,怎么进行插入呢?Insert Interval条件太多,每一个大小等号比较,每一个小下标就能让人栽跟斗,因此它也是我目前最讨厌的题目,没有之一。
一开始尝试这种思路:
“新序列按照start排好序(start肯定是各不相同的),第一步我们先用二分找出有交集的序列片段的开始,这一点很像Search Insert Position,然后再往后处理。”
脑子不清楚憋了一下午,恶心的我两天不能刷Leetcode,如果真要写出来的话,就老老实实下面这样,效率不一定差,因为看题目反正是不想要你改变输入参数,横竖都得遍历一遍来拷贝。挺有意思的是,晚上我看到了Google Campus的youku视频,讲述的就是一个倒霉孩子花了30min写二分Insert Interval的反例。。。
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
vector<Interval> rs;
int i = ;
while(i < intervals.size() && intervals[i].end < newInterval.start){//找到第一个起点
rs.push_back(intervals[i++]);
}
if(i == intervals.size()){//为空或过了结尾点
rs.push_back(newInterval);
return rs;
} newInterval.start = min(newInterval.start, intervals[i].start);
while(i < intervals.size() && intervals[i].start <= newInterval.end){//找到结束点
newInterval.end = max(newInterval.end, intervals[i++].end);
}
rs.push_back(newInterval); while(i < intervals.size()){
rs.push_back(intervals[i++]);
}
return rs;
}