When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Overlapping ranges
- Schedules
- Coverage
When another approach fits better
- The question is about arbitrary point updates/queries
- Intervals arrive online and require a dynamic index beyond one batch sort
How it works#
Repeatedly compare and merge every interval pair until no overlaps remain.
Clarify closed/half-open endpoints and touching behavior.
Sort by start, with a deliberate tie rule if needed.
Compare each interval with the current merged boundary, extending it or emitting it.
InvariantThe output prefix is fully merged and nonoverlapping; the current interval covers every processed input not already emitted.
Example and template#
Merge Intervals
Sort first, then compare each range with the active merged boundary.
Open the full problem brief- Current
[1,5]It covers all un-emitted processed ranges.
- Read [4,8]
[1,8]The start overlaps the current end, so extend with the maximum end.
sort intervals by start
merged = []
for interval in intervals:
if merged empty or interval.start > merged.last.end:
append copy(interval)
else:
merged.last.end = max(merged.last.end, interval.end)- Time
- O(n log n)
- Space
- O(n) output; extra space depends on sort
- Assumptions
- Batch input can be sorted and endpoint comparisons follow the declared overlap convention.
Pitfalls#
Common wrong approaches
A merged interval may extend past several later intervals and must remain the comparison boundary.
Whether [1,2] overlaps [2,3] depends on endpoint semantics.
Edge cases
- Nested intervals
- Equal starts
- Touching endpoints
- Empty input
Interview narration
- “Sorting by start makes any possible overlap occur against the current merged range.”
- “The output before the current range is final and disjoint.”
- “This range overlaps, so only the farthest end matters.”
Practice#
Merge Intervals
Sort first, then compare each range with the active merged boundary.
Practice this problemGiven meeting times, return the minimum number of rooms needed.
Reveal the pattern decision
Intervals are present, but merging loses concurrency; use sorted events or a heap of active end times.
Transfer problem
Insert one interval into an already sorted disjoint list.
Checkpoint: Emit ranges before it, merge all overlaps, then emit the untouched suffix without resorting.
Follow-up variations
- Compute total covered length
- Handle open/closed endpoints explicitly
Error-log prompts
- What did touching mean?
- Did I compare against the merged boundary?