Merge overlapping intervals (e.g. promotion periods)

# ======================================================================
# Q: Merge overlapping intervals (e.g. promotion periods).
#
# O(n log n) because of the sorting.
# ======================================================================

def merge(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    result = []
    for start, end in sorted(intervals):
        if result and start <= result[-1][1]:
            result[-1] = (result[-1][0], max(result[-1][1], end))
        else:
            result.append((start, end))
    return result

merge([(1, 3), (2, 6), (8, 10), (9, 12)])   # [(1, 6), (8, 12)]