PYTHON & CODING · QUESTION 89
How do you merge overlapping intervals?
On this page
Sort intervals by start time, then scan from left to right while keeping the latest merged interval. If the next interval starts before or at the current end, extend the end to the larger endpoint; otherwise, append a new interval. Sorting costs O(n log n), and the scan is O(n). Clarify whether touching endpoints count as overlap.
LET'S MAKE IT SIMPLE
First, the idea in plain English
Intervals overlap when their ranges share part of the timeline or number line. Sorting by start puts possible overlaps next to each other. Then a single pass can either extend the current range or finish it and begin another.
A USEFUL COMPARISON
Picture it this way
Imagine merging overlapping blocks of booked meeting time on a calendar. Once appointments are sorted by start, each new block either extends the current busy period or starts a separate one.
FOLLOW THE JOURNEY
Sort intervals, then extend or finalize the current range
Trace overlap checks and merged range updates.
This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; One pass produces disjoint merged ranges.
Intervals sorted by start are scanned; overlapping ranges extend the current end, while a disjoint interval starts a new merged range.
How to read this visual
This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; One pass produces disjoint merged ranges.
UNDER THE HOOD
How it works, step by step
Sort by start
Order intervals by their starting endpoint.
Why it matters: Potential overlaps become adjacent in the scan.
Compare next interval
Check whether its start is within the current merged end.
Why it matters: This determines whether ranges connect.
Extend or append
Increase the end for overlap or finalize and start a new interval.
Why it matters: One pass produces disjoint merged ranges.
OUTSIDE THE TEXTBOOK
A practical example
Maintenance windows [1, 4], [3, 6], and [8, 10] become [1, 6] and [8, 10]. The first two overlap and merge; the third starts after a gap. If intervals are half-open, endpoint equality may not count as overlap and the condition changes.
GO A LITTLE DEEPER
Technical details that matter
- Sorting dominates at O(n log n); the scan is linear and uses O(n) output space.
- For closed intervals, `[a, b]` and `[b, c]` touch and often merge; half-open interval conventions differ.
- Malformed intervals with start greater than end should be rejected or normalized according to the contract.
def merge_intervals(intervals):
merged = []
for start, end in sorted(intervals):
if not merged or start > merged[-1][1]:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
return mergedThis implementation treats touching endpoints as overlapping for closed intervals. Sorting and scanning takes O(n log n) time.
MAKE A GOOD CHOICE
When is this useful?
- Combining calendar availability or booking windows.
- Merging ranges in logs, genomic coordinates, or numeric coverage.
- Normalizing overlapping time windows before querying.
For already sorted intervals, skip sorting and scan in O(n). For online insertions, an ordered interval structure may be more appropriate.
WATCH OUT FOR
Common misunderstandings
- Not sorting before the scan.
- Replacing the current end with a smaller endpoint instead of taking the maximum.
- Ignoring closed versus half-open endpoint semantics.
REAL-WORLD TRADE-OFFS
Limitations and failure cases
- The result requires output storage proportional to interval count.
- Sorting can dominate for large inputs.
- The simple algorithm assumes one-dimensional intervals with a clear ordering.
WHAT TO REMEMBER
Key takeaways
- 1Sort by start, then scan once.
- 2Extend the current end when ranges overlap.
- 3State endpoint semantics and validate malformed ranges.
PRACTICE THE FOLLOW-UP
What might an interviewer ask next?
What is the time complexity?
Sorting costs O(n log n), and the merge scan costs O(n), so total time is O(n log n). The output can use O(n) space.
What if intervals are already sorted?
The sorting step is unnecessary, so a single scan takes O(n) time.
SAY IT OUT LOUD
How to explain this in an interview
“I sort intervals by start, then keep a current merged range. If the next interval overlaps, I extend the end to the larger endpoint; otherwise I append the current range and start another. The scan is linear after sorting, so total time is O(n log n). I would clarify whether touching endpoints count as overlap.”
Connect this question to the roadmap topic it supports.