Merge overlapping intervals

Sort by start, then sweep, extending the current interval while the next one begins before it ends.

sort a by start
out = []
for iv in a:
    if out and iv.start <= out[-1].end:
        out[-1].end = max(out[-1].end, iv.end)
    else:
        out.append(iv)
return out

Why sorting by start is enough. After sorting, any interval that overlaps the one currently being built must start at or before its end. Every later interval starts even further right, so once one fails to overlap, none of the rest can either — the current interval is finished and can be emitted. That is the argument that makes a single pass correct.

The max matters. A fully contained interval like [1, 10] followed by [2, 3] would otherwise shrink the end to 3. This is the most common mistake in an otherwise correct solution.

Closed versus half-open. With closed intervals [1,3] and [3,5] touch and merge into [1,5]; the test is <=. With half-open [start, end) they do not, and the test is <. Both are defensible — saying which convention you are using, and being consistent, is the answer. Silently picking one is where candidates lose the point.

O(n log n) for the sort, O(n) for the sweep.