Merge Overlapping 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]
.
Make sure the returned intervals are sorted.
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
bool cmp(Interval &a,Interval &b){
if(a.start==b.start)return a.end<b.end;
return a.start<b.start;
}
vector<Interval> Solution::merge(vector<Interval> &v) {
vector<Interval>ans;
sort(v.begin(),v.end(),cmp);
Interval s=v[0];
for(int i=1; i<v.size(); i++){
if(v[i].start>s.end){
ans.push_back(s);
s=v[i];
}
else if(v[i].start<=s.end){
s.end=max(s.end,v[i].end);
}
}
ans.push_back(s);
return ans;
}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.