Overlapping Intervals
Given a collection of Intervals, the task is to merge all of the overlapping Intervals.
- Time : O(nlogn)
- Space : O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| class Solution { map<int, int> intervals; map<int, int>::iterator front(int s) { auto it = intervals.upper_bound(s); if(it == begin(intervals)) return intervals.insert({s,s}).first; --it; if(it->second >= s) return it; return intervals.insert({s,s}).first; } void merge(int s, int e) { auto start = front(s); start->second = max(start->second, e); while(next(start) != end(intervals)) { auto nxt = next(start); if(start->second >= nxt->first) { start->second = max(start->second, nxt->second); intervals.erase(nxt); } else break; } } public: vector<vector<int>> overlappedInterval(vector<vector<int>> &ranges) { for(auto& range : ranges) { merge(range[0], range[1]); } vector<vector<int>> res; for(auto interval : intervals) { res.push_back({interval.first, interval.second}); } return res; } };
|