https://leetcode.com/problems/merge-intervals/description/

(Sorting) Python

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    # sorting ensures start times are in chronological order
    # so all you need to check is if the end time of the 
    # previous interval is greater than the start the of the
    # current interval
    intervals.sort(key=lambda x: x[0])

    merged = []
    for interval in intervals:
        # if there is nothingin merged or the end time of the
        # previous interval is greater than the start time
        # of the current interval, there is no overlap
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        # there is overlap
        else:
            # update the end time of previous interval to the
            # max end time of the previous and current interval
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    return merged

(Sorting) C++

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;

        for (auto interval:intervals){
            // no overlap
            if (merged.empty() || merged.back()[1] < interval[0]){
                merged.push_back(interval);
            }
            // overlap
            else{
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }

        return merged;
    }
};

$Time = O(N * log N)$

Other than the sort invocation, we do a simple linear scan of the list, so the runtime is dominated by the complexity of sorting.

$Space = O(logN)$ or $O(N)$

If we can sort intervals in place, we do not need more than constant additional space, although the sorting itself takes $O(log N)$ space. Otherwise, we must allocate linear space to store a copy of intervals and sort that.