DSA Tracker

Visualize

Merge Intervals

Sort by start, then sweep and absorb overlaps

time O(n log n)space O(n)

Sorting by start gives one powerful guarantee: an interval can only overlap the LAST interval in the merged output — everything earlier already ends before it starts. So one sweep with one comparison per interval (next.start vs last.end) decides everything: overlap means grow last's right edge, gap means last is sealed forever.

Details

Animated on: Merge Intervals: combine all overlapping intervals in [8-10, 1-3, 15-18, 2-6, 9-12] into the minimal set of disjoint intervals.

Problem:Merge IntervalsMedium

Pattern:Intervals

Sort by start, then sweep and absorb overlaps

step 1 / 11

8-10
[0]
1-3
[1]
15-18
[2]
2-6
[3]
9-12
[4]

Raw input. Overlapping pairs like 8-10 and 9-12 sit at opposite ends — no neighbor check can catch them here. Sort by start first, so every overlap is forced to be with an adjacent interval.

Pseudocode
1FUNCTION merge(intervals):
2  sort intervals by their start value
3  merged = a list holding just the first interval
4  FOR each next interval after the first:
5    last = the last interval in merged
6    IF next.start <= last.end:  (they overlap)
7      last.end = the larger of last.end and next.end
8    ELSE: add next to merged as a new interval
9  RETURN merged

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Raw input. Overlapping pairs like 8-10 and 9-12 sit at opposite ends — no neighbor check can catch them here. Sort by start first, so every overlap is forced to be with an adjacent interval.
  2. Sorted by start. Seed merged with 1-3 — it is the open interval last. From now on, if next misses last it misses everything before it too, so one comparison per interval suffices.
  3. next = 2-6. Overlap test is just next.start <= last.end: 2 <= 3, so the two share the range 2..3 — they must become one interval.
  4. Absorb instead of push: last.end = max(3, 6) = 6, so 1-3 grows into 1-6. Absorbing keeps the output disjoint — five cells just became four.
  5. next = 8-10. 8 > 6, so no overlap with 1-6 — and because starts are sorted, every later interval starts at 8 or beyond. 1-6 can never grow again.
  6. Gap: seal 1-6 into the answer (green) and push 8-10 as the new open interval. merged = [1-6, 8-10]; last now points at 8-10.
  7. next = 9-12. 9 <= 10 — its start lands inside 8-10, so they overlap on 9..10 and must merge.
  8. last.end = max(10, 12) = 12 → 8-12. The max matters: 9-12 starts inside 8-10 but reaches PAST it, stretching the right edge. (Had next been fully inside, max would correctly leave the edge alone.)
  9. next = 15-18. 15 > 12 — a gap again, so 8-12 is finished for good.
  10. Seal 8-12, push 15-18 as the new open interval. merged = [1-6, 8-12, 15-18] — and the input is exhausted.
  11. Answer: [1-6, 8-12, 15-18]. Five intervals merged into three disjoint ones. The sort's O(n log n) dominates; the sweep itself touches each interval exactly once.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Merge Intervals in the editorAll Intervals problemsBack to roadmap