Big O Practice: Merge Intervals

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    res = []
    for start, end in intervals:
        if res and start <= res[-1][1]:
            res[-1][1] = max(res[-1][1], end)
        else:
            res.append([start, end])
    return res

Variables

• n - number of input intervals

Explanation

Sorting dominates - **O(n log n)**. The sweep itself is linear. Output (and sort scratch) take **O(n)** space.

More Big O practice problems · Today's daily problem