Overlapping Intervals

Given a collection of Intervals, the task is to merge all of the overlapping Intervals.

• Time : O(nlogn)
• Space : O(n)

c++

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;
    }
};