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:
static bool compare(const Interval &first,const Interval &second)
{
if(first.start==second.start)
return first.end<second.end;
else
return first.start<second.start;
}
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> ret;
int n=intervals.size();
int pre=, cur=;
sort(intervals.begin(),intervals.end(),compare);
while(cur<n)
{
while(cur<n&&intervals[pre].end>=intervals[cur].start)
{
intervals[pre].start=min(intervals[pre].start,intervals[cur].start);
intervals[pre].end=max(intervals[pre].end,intervals[cur].end);
cur++;
}
ret.push_back(intervals[pre]);
pre=cur; }
return ret;
}
};