Merge Intervals
Merge every overlapping interval.
Why does this pattern fit?
Restate the exact job
Merge every overlapping interval.
After sorting by start, only the last merged interval can overlap the next.
O(n log n) time · O(n) output
Sorting by end does not expose overlaps in one forward pass.
How to solve Merge Intervals
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Merge every overlapping interval.
Why Intervals & sweep line fits
After sorting by start, only the last merged interval can overlap the next.
State to maintain
Sorted intervals and an output stack.
Transition
Extend the last end on overlap; otherwise append a new interval.
Time and space
O(n log n) time · O(n) output
Counterexample to the tempting mistake
Sorting by end does not expose overlaps in one forward pass.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.