Problem
Given a collection of intervals, merge all overlapping intervals.
For example,
Given
return
Given
[1,3],[2,6],[8,10],[15,18]
,return
[1,6],[8,10],[15,18]
.Code
class Comp { public: bool operator()(const Interval &i1,const Interval &i2){ return (i1.start < i2.start); } }; class Solution { public: vector<Interval> merge(vector<Interval> &intervals) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. vector<Interval> result; sort(intervals.begin(),intervals.end(),Comp()); int n = intervals.size(); int i = 0; while(i < n){ int j = i; int finish = intervals[j].end; while(j < n - 1 && finish >= intervals[j + 1].start){ ++j; finish = max(finish,intervals[j].end); } result.push_back(Interval(intervals[i].start,finish)); i = j + 1; } return result; } };
No comments:
Post a Comment