vizlearn

Merge overlapping intervals

Interview QuestionsBy Updated

Sort by start. After that an interval can only overlap the one immediately before it, so a single pass merges everything: extend the last kept interval if it reaches this one, otherwise start a new one. O(n log n) for the sort, O(n) after it.

Overview

Why sorting collapses the problem

Unsorted, any interval can overlap any other, so you are looking at pairs — O(n²). Sorted by start, an interval's only possible overlap is with the merged block immediately behind it, because everything earlier starts earlier and has already been absorbed.

That reduces the whole thing to one comparison per interval. The sort costs O(n log n) and dominates.

Lists & arraysCoding problemMedium

Step through it

What to watch

  • Sorting is the whole trick — without it every pair must be compared.
  • Only the last merged interval is ever checked.
  • Extending takes the larger end, not this interval's end.

Say this out loud

"Sort by start, then sweep. Each interval either extends the last merged one or starts a new one. The sort dominates, so O(n log n)."

Merge overlapping intervals

Given a list of intervals, merge the ones that overlap.

The line people get wrong

When extending, take max(last_end, this_end), not this_end. A fully contained interval — [1, 10] then [2, 3] — would otherwise shrink the merged block to 3 and silently lose everything from 3 to 10.

The other decision is whether touching counts as overlapping. [1, 3] and [3, 5] merge under lo <= last_end and stay separate under <. Both are defensible; ask which the question wants.

What it generalises to

Meeting rooms, calendar conflicts, genome ranges, IP blocks — all the same sweep. The variants change only the merge rule: count how many rooms are needed simultaneously (a sweep line with +1 and −1 events), insert one interval into an already-merged list, or find the gaps rather than the blocks.

Run it in Python

The sweep with each decision printed, the contained-interval case that breaks the naive extend, and both answers to the touching question.

merge_intervals.pyPython 3
Output
How the code works
  1. sorted(intervals)The whole reduction. Sorted by start, an interval can only overlap the merged block directly behind it, so one comparison per interval replaces comparing every pair.
  2. last[1] = max(last[1], hi)The max is load-bearing. [1, 10] followed by [2, 3] would otherwise shrink the block to 3 and silently drop everything up to 10.
  3. lo <= last[1] versus lo < last[1]Whether [1,3] and [3,5] merge. Both conventions are used; the question usually implies one, and asking is a better move than guessing.
  4. events.sort() in max_overlapThe sweep-line variant: +1 when an interval opens, −1 when it closes, and the running total is how many are live at once. Same sort, different question.
Change one thing
  • Feed it intervals already sorted by end instead. The sweep gives wrong answers — the precondition is specifically sorted by start.
  • Write insert(intervals, new) for an already-merged list. It is O(n) with no sort, and a common follow-up.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why does sorting by start make one pass sufficient?
  2. Why must the extend use max(last_end, this_end)?
  3. The overall complexity is:





 Cheat sheet
Merge overlapping intervals
Sort by start. After that an interval can only overlap the one immediately before it, so a single pass merges everything: extend the last kept interval if it reaches this one, otherwise start a new one. O(n log n) for the sort, O(n) after it.
INTERVIEW · vizlearn.in/interview/merge-intervals.html
More in Interview
InterviewFind the duplicate numberInterviewKth largest elementInterviewTrapping rain waterInterviewSort an array of 0s, 1s and 2s
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact