Merge Overlapping Intervals

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

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
vector<Interval> Solution::merge(vector<Interval> &A) {
    sort(begin(A), end(A), [](auto a, auto b) {
        return a.start < b.start;
    });
    vector<Interval> res;
    for(auto& a : A) {
        if(res.empty() or res.back().end < a.start) res.push_back(a);
        else res.back().end = max(res.back().end, a.end);
    }
    return res;
}