Pattern visualizer

Merge Intervals

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. 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..

Sort by start, then sweep and absorb overlaps

time O(n log n)space O(n)step 1 / 11

8-10

[0]

1-3

[1]

15-18

[2]

2-6

[3]

9-12

[4]

line 2

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

Where to practice Intervals

Practice Intervals problems All Intervals problems Back to roadmap