DATA STRUCTURES • ALGORITHMS

Merge Intervals

Given a collection of intervals, merge all overlapping intervals into a single range.

Time

O(N log N) (due to sorting)

Space

O(N) (to store results)

Key Principle 1

Sort intervals by start time

Key Principle 2

Compare current end with next start

Key Principle 3

Update end to max(end1, end2)

Key Principle 4

Handles discrete and continuous ranges

MERGE_INTERVALS_LAB
INTERVALS:
Current Step
Sort intervals by start time. Initialize with first interval.
Playback
Merge Logic ⠿
1sort(intervals);
2merged.push(intervals[0]);
3for (auto next : intervals) {
4    auto& last = merged.back();
5    if (next.start <= last.end) {
6        last.end = max(last.end, next.end);
7    } else {
8        merged.push(next);
9    }
10}
Input Intervals (Sorted)
[1, 3]
[2, 6]
[8, 10]
[15, 18]
Merged Result

Loading Lab...