Optimal Python Solution for Merge Intervals (Interview Script)

2025-09-29

The Logic

• Overlapping intervals only matter when they are adjacent after sorting.
• Sorting by start time converts the problem into a single linear pass.
• Maintain a current interval and extend it when overlap occurs.

Implementation / Diagram

Key Invariant

At any point, the current interval represents the merged result of all overlapping intervals seen so far.

def merge(intervals):
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last_end = merged[-1][1]

        if start <= last_end:
            merged[-1][1] = max(last_end, end)
        else:
            merged.append([start, end])

    return merged