For example,
Given
[1,3],[2,6],[8,10],[15,18]
,return
[1,6],[8,10],[15,18]
.Solution: sort the input intervals in term of starts first, then scan the intervals and merge overlapped intervals. Note: Leetcode prohibit passing the function pointer as the third argument of sort routine. The function objector is the unique choice.
/** * 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: class compare{ public: bool operator()(Interval a, Interval b){ return a.start<b.start; } }; vector<Interval> merge(vector<Interval> &intervals) { // Note: The Solution object is instantiated only once and is reused by each test case. vector<Interval> ret; if(intervals.empty()) return ret; //sort the intervals sort(intervals.begin(), intervals.end(), compare()); ret.push_back(intervals[0]); for(int i=1; i<intervals.size(); i++){ if(intervals[i].start>ret.back().end) ret.push_back(intervals[i]); else ret.back().end = max(ret.back().end, intervals[i].end); } return ret; } };
No comments:
Post a Comment