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:
struct cmp{
bool operator()(const Interval& x, const Interval& y) const
{
if(x.start != y.start) return x.start < y.start;
else return x.end < y.end;
}
};
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> result;
if(intervals.empty())return result;
sort(intervals.begin(), intervals.end(),cmp());
Interval cur = intervals[0];
for(int i=1;i<intervals.size();i++)
{
if(cur.end < intervals[i].start)
{
result.push_back(cur);
cur = intervals[i];
}else{
cur.end = max(cur.end,intervals[i].end);
}
}
result.push_back(cur);
return result;
}
};