Interval的合并时比较常见的一类题目，网上的Amazon面经上也有面试这道题的记录。这里以LeetCode上的例题做练习。
Merge Intervals
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].
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
}
};
我的解法是新定义一个vector<Interval> res，然后每次从intervals中提一个Interval出来，如果这个Interval和res中已有的某个Interval有overlap，就合并成新的Interval，又放回intervals中。
循环终止条件是intervals.size() == 0。
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> res;
while(intervals.size() > ){
Interval inv = intervals.back();
intervals.pop_back();
vector<Interval>::iterator i = res.begin();
vector<Interval>::iterator rend = res.end();
for(; i < rend; ++i){
if(!((*i).start > inv.end || inv.start > (*i).end)){
(*i).start = min((*i).start, inv.start);
(*i).end = max((*i).end, inv.end);
intervals.push_back(*i);
res.erase(i);
break;
}
}
if(i == rend){ //事先将res.end()保存为rend很有必要，因为res.end()此时已经变化了。
res.push_back(inv);
}
}
return res;
}
};AC 80ms
但上面的解法需要把一个Interval在两个vector间移来移去，而且每次从intervals取出后，又要从res的头部开始比较，比较费时间。最好当然是每次从intervals中取出一个Interval后，就将res中所有的都遍历完并合并。
这样的代码：
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> res;
if(intervals.size() == ) return res;
for(vector<Interval>::iterator it = intervals.begin(); it != intervals.end(); ++it){
Interval* interval = new Interval(it -> start, it -> end);
for(vector<Interval>::iterator it2 = res.begin(); it2 < res.end();){
if(!(interval -> end < it2 -> start || it2 -> end < interval -> start)){
interval -> start = min(interval->start, it2->start);
interval -> end = max(interval->end, it2->end);
it2 = res.erase(it2);
}else ++it2;
}
res.push_back(*interval);
}
return res;
}
};AC 56ms
上面两种解法都是新定义一个vector用来存放结果。如果不新定义vector直接在原intervals上操作呢？这种解法参考了tenos的解法。
先将intervals按照start 升序排序，然后it1指向begin()，接着it2 指向it1的下一个元素，如果it2 和 it1有重叠，就把it2的区间算入 it1的区间，接着++it2，直到it2的区间和it1 没有重叠。
因为it2 走过的部分都已经被算入it1里，所以it1+1到当前it2的部分可以被删除了。
接着继续重复上述步骤，直到it1 或者 it2到达末尾。
这种解法要求 intervals 必须是有序的。
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
if(intervals.size() <= ) return intervals;
sort(intervals.begin(), intervals.end(), compare);
vector<Interval>::iterator it1 = intervals.begin();
vector<Interval>::iterator it2 = it1 + ;
while(it1 != intervals.end() && it2 != intervals.end()){
if(!(it2 -> end < it1 -> start || it1 -> end < it2 -> start)){
it1 -> start = min(it1 -> start, it2 -> start);
it1 -> end = max(it1 -> end, it2 -> end);
++it2;
}else{
it1 = intervals.erase(it1 + , it2);
it2 = it1 + ;
}
}
if((it1+) != it2) intervals.erase(it1 + , it2);
return intervals;
}
private:
static bool compare(Interval a, Interval b){
return (a.start < b.start);
}
};AC 60ms 因为在原vector上操作，所以比起解法二 略慢了一些。
基于Merge，会衍生出一些题目，比如下面的Insert。
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].
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
}
};
因为原vector 所包含的Interval是有序排列的，我们只要先将newInterval 放入 该放的地方，然后向后合并就可以。
class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
vector<Interval>::iterator it1 = intervals.begin();
for(; it1 != intervals.end() && it1 -> end < newInterval.start; ++it1); //放入该放的地方
it1 = intervals.insert(it1, newInterval);
vector<Interval>::iterator it2 = it1 + ;
for(; it2 != intervals.end(); ++it2){
if(!(it2 -> end < it1 -> start || it1 -> end < it2 -> start)){
it1 -> start = min(it1-> start, it2 -> start);
it1 -> end = max(it1 -> end, it2 -> end);
}else break; //如果it2不再和it1重叠，因为intervals有序排列，所以it2后面的Interval肯定也不和it1重叠，可以退出循环了。
}
if(it2 != (it1 + )) intervals.erase(it1+, it2); //删除it2走过的部分。
return intervals;
}
};总结：
通过这两题，(1) 首先我们需要熟练掌握一个基本的判断两个Interval是否overlap的方法： if(!((*i).start > inv.end || inv.start > (*i).end))
(2) 使用vector 的iterator方法遍历时，如果遍历的同时存在vector的大小更改，需要特别注意大小更改对 .end() 结果的影响，最好先将.end() 保存下来，除非你确实需要 .end()的动态变化作为比较值。
(3) 若在遍历vector时使用erase或者insert，因为vector大小被更改，因此原来的iterator会失效，需要将iterator 赋值为erase 和 insert 的返回值。
erase返回的值为删除当前 iterator 指向的元素后，下一个元素所在的地址。
insert返回的值为新增元素所在的地址(仅限于insert 一个元素的情况)。