Merge Intervals

Sort + Linear Sweep

1:00

How to collapse a pile of potentially-overlapping ranges into the fewest disjoint blocks using a sort-then-sweep in O(n log n).

By the end, you can

Explain why sorting by start transforms the problem from O(n²) to O(n log n).
State and apply the overlap test: `s2 <= e1` (not strict `<`).
Trace the merge-sweep algorithm on a given sorted input, tracking the current merged end.
Identify why `max` is used when extending the end and what goes wrong without it.
Handle the three edge cases: touching endpoints, fully-nested intervals, and empty input.
Describe the Insert Interval strategy (before / merge-overlaps / after) and its complexity.

Up next in Coding Interview Patterns