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]
.
思考:先排序。比较相邻两个interval,left为前一个start,若后一个start小于等于前一个,说明这两个interval需要合并,right为两个end较大者。若后一个start大于前一个end,说明这两个interval不需要合并,输出前一个。
/** * 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 comp(const Interval &a,const Interval &b) { return a.start<b.start; } class Solution { private: vector<Interval> ret; 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. ret.clear(); int len=intervals.size(); if(len==0) return ret; if(len==1) {ret.push_back(intervals[0]);return ret;} sort(intervals.begin(),intervals.end(),comp); int left=intervals[0].start; int right=intervals[0].end; for(int i=1;i<len;i++) { if(intervals[i].start<=right) right=max(right,intervals[i].end); if(intervals[i].start>right) { // cout<<left<<" "<<right<<endl; ret.push_back(Interval(left,right)); left=intervals[i].start; right=intervals[i].end; } if(i==len-1){ // cout<<left<<" "<<right<<endl; ret.push_back(Interval(left,right));} } return ret; } };