Solutions

# Sort by start time then merge intervals if they overlap. Or sweep line alogorithm (tracking number of active intervals at each point in time).
# intervals

# O(N log N) time, O(N) space
def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    
    out = []
    for start, end in intervals:
        if not out or out[-1][1] < start:
            out.append([start,end])
        else:
            out[-1][1] = max(out[-1][1], end)

    return out

# Sweep line algorithm - O(N log N) time, O(N) space
# Track the number of active intervals at each point in time.
# When we go from 0 active intervals to 1 active interval, we start a new merged interval.
# When we go from 1 active interval to 0 active intervals, we end the current merged interval.
def merge(intervals: list[list[int]]) -> list[list[int]]:
    from collections import defaultdict
    mp = defaultdict(int)
    for start, end in intervals:
        mp[start] += 1
        mp[end] -= 1

    res = []
    interval = []
    have = 0
    for i in sorted(mp):
        if not interval:
            interval.append(i)
        have += mp[i]
        if have == 0:
            interval.append(i)
            res.append(interval)
            interval = []
    return res

# There's also a greedy algorithm O(n + m) time, but it's complex.