Algorithms
Merge Intervals
O(n log n) time to sort, then O(n) time to merge in one pass · O(n) space for the result.
The idea, in plain English
Imagine a list of meeting times on your calendar, and some overlap — like 9 to 10am and 9:30 to 11am. Merging intervals means combining any that overlap into one longer block, so your calendar shows the fewest possible non-overlapping chunks of busy time.
How it works
- 1Sort the intervals, the time ranges, by their start time.
- 2Walk through them one by one, keeping track of a 'current merged' interval.
- 3If the next interval starts before, or exactly when, the current one ends, stretch the current one to cover both. Otherwise, close out the current merged interval and start a new one.
When you'd use it
Use it to combine overlapping ranges — merging busy calendar slots, combining overlapping time windows in logs, or simplifying a list of numeric ranges before you process them.
Common beginner mistakes
- Forgetting to sort by start time first. The one-pass merge only works because the intervals arrive in order.
- Using strict less-than instead of less-than-or-equal when you check for overlap. This misses back-to-back intervals that touch exactly at the boundary, like [1, 3] and [3, 5].
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
Merged: 1-6 8-12 15-18See it in motion
Sorted by start time first — the single-pass sweep only works in order.
Sorted by start time. Press play to sweep left-to-right and merge overlaps.
Not sure this is the right topic? See the learning paths → or where this leads →