What is the Merge Intervals Pattern?
Merge Intervals turns a collection of ranges into a smaller collection with no overlaps. Sorting by start places intervals that can interact next to one another.
You need sorting and simple array scans. The short version is: sort by start, keep one active interval, and either extend it or close it.
The Core Idea: Keep One Active Range
In Basic Merge, the first two intervals are [1,3] and [2,6].
The second interval starts at 2, before the active interval ends at 3.
What should the merged interval be?
It starts at 1 and must reach the farther end, 6, so it becomes [1,6].
The next interval [8,10] begins after 6, so [1,6] is finished.
It is like combining bookings on a calendar. While the next booking begins before the current occupied block ends, the room remains occupied for one continuous block.
How the Active Interval Changes
The Rule You Keep True
The output contains every completed merged interval from the processed prefix, and active is the only processed interval that may still overlap future input.
Sorting makes that single active interval sufficient.
Related interval questions change the action after sorting:
- Merge overlaps extends the active end.
- Meeting room counting tracks how many intervals are active at once.
- Remove overlaps keeps the interval whose end leaves the most room for future intervals.
- Insert interval merges the new range with every overlapping neighbor.
Nested Intervals is the one that usually trips us up.
When [2,4] sits inside [1,10], the active end must stay 10.
Assigning the next end directly would accidentally shrink the merged range.
Picking the Right Shape
From Rule to Code
- Sort intervals by start, with a clear tie rule if needed.
- Use the first interval as the active range.
- Compare each next start with the active end.
- Extend the active end on overlap, otherwise save it and begin a new active range.
- Save the final active range after the scan.
Sorting costs O(n log n) and the merge scan costs O(n), while the result uses up to O(n) space.
When to use it
- •The input contains ranges with starts and ends.
- •Overlapping ranges must be combined, counted, scheduled, or removed.
- •Sorting by one endpoint makes conflicts appear next to each other.
- •The answer depends on whether one interval begins before another active interval ends.
How to identify it
- •The prompt mentions intervals, meetings, bookings, ranges, or schedules.
- •Each item can be represented as `[start, end]`.
- •The main comparison is between the next start and the current end.
- •Unsorted input hides which ranges can interact.
Key insights
- →Sort intervals by start so every possible overlap with the active interval appears next.
- →If the next start is at most the active end, the intervals overlap under the usual inclusive rule.
- →Merging keeps the active start and extends its end to the larger end.
- →A non-overlapping interval closes the active interval and starts a new one.
- →Different problems may treat touching endpoints as overlapping or separate, so the comparison must match the prompt.
Common mistakes
- 01Scanning unsorted intervals and missing overlaps that are far apart in the input.
- 02Replacing the active end with the next end instead of taking the maximum.
- 03Forgetting to append the final active interval after the loop.
- 04Assuming `[1,2]` and `[2,3]` overlap without checking the problem's endpoint rule.
- 05Using the merge rule for an interval-removal problem that needs a different greedy choice.