Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
http://www.lintcode.com/en/problem/merge-intervals/#
Discussion
先根据start排序，逐次插入interval，注意是否overlap，关于怎么判断overlap在Insert Interval里面已经说了。排序interval的时候需要自定义一个Comparison structure，注意sort函数里面用的是Comparison object。
Solution
//O(nlogn) rum time
//O(n) space
/**
* Definition of Interval:
* classs Interval {
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
*/
class Solution {
public:
/**
* @param intervals: interval list.
* @return: A new interval list.
*/
struct cmpInterval {
bool operator() (const Interval &A, const Interval &B) const {
if(A.start == B.start) return A.end < B.end;
return A.start < B.start;
}
};
vector<Interval> merge(vector<Interval> &intervals) {
if(intervals.empty()) {
return intervals;
}
//sort intervals accoring to start values
sort(intervals.begin(), intervals.end(), cmpInterval());
//when merge, two cases:
//1. non-overpal : pre.end < next.start, pre is always the end of result
//2. overlap : find max of (prev.end, next end) as the new end of current interval
vector<Interval> result = {intervals[0]};
Interval pre = intervals[0];
for(int i=1; i<intervals.size(); i++) {
Interval cur = intervals[i];
if(pre.end < cur.start) {//non overlap
result.emplace_back(cur);
} else {
int newend = max(pre.end, cur.end);
result.back().end = newend;//cannot update pre directly
}
//pre = cur;//这里错了，cur不一定查到队尾了啊！
pre = result.back();
}
return result;
}
};
Follow up
能不能做到in-space呢？
class Solution {
public:
/**
* @param intervals: interval list.
* @return: A new interval list.
*/
struct CmpInterval {
bool operator() (const Interval& A, const Interval&B) const {
return A.start < B.start;
}
};
vector<Interval> merge(vector<Interval> &intervals) {
if(intervals.size()<2) return intervals;
sort(intervals.begin(), intervals.end(), CmpInterval());
int j = 0; //index of the merged intervals
for(int i=1; i<intervals.size(); i++) {
if(intervals[j].end < intervals[i].start) {//non overlap
j++;
intervals[j].start = intervals[i].start;
intervals[j].end = intervals[i].end;
} else {
intervals[j].end = max(intervals[j].end, intervals[i].end);
}
}
intervals.erase(intervals.begin()+j+1, intervals.end());
return intervals;
}
};
About sort function
- 上面是定义了一个comparison structure，然后sort函数里comparison oject是sort的第三个参数，cmpInterval()代表一个object。
- 也可以用一个function pointer来取代cmpInterval(), as follows:
bool CompareInterval(Interval A, Interval B) { if(A.start == B.start) return A.end < B.end; return A.start < B.start; } - 诡异的是A B不能像cmpInterval里面那样引用传递。
- 更诡异的是这个function的定义不能放到solution里面，只能放到Solution class外面。要放到solution里面的话要在定义前面加上static关键字
A quote from the book is that "the most important feature of static member function is that it doesn't have "this pointer", so here if we use a static member function as compare function for sort, it works just exactly like nonmember function!
- 也可以用nabla function来代替comparison function。
[](const Interval& A, const Interval& B){return A.start < B.start;}