Given a collection of intervals, merge all overlapping intervals.
Example
Given intervals => merged intervals:
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]
Challenge
O(n log n) time and O(1) extra space.
/** * Definition of Interval: * classs Interval { * int start, end; * Interval(int start, int end) { * this->start = start; * this->end = end; * } */ class Solution { static bool compFunc(const Interval &i1, const Interval& i2) { return i1.start < i2.start; } public: vector<Interval> merge(vector<Interval> &intervals) { int size = intervals.size(); vector<Interval> res; if(0 == size) return res; sort(intervals.begin(), intervals.end(), compFunc); res.push_back(intervals[0]); for(int i=1;i<size;i++) { if(!(res.back().start>intervals[i].end || res.back().end < intervals[i].start)){ res.back().start = min(res.back().start, intervals[i].start); res.back().end = max(res.back().end, intervals[i].end); } else{ res.push_back(intervals[i]); } } return res; } };