Merge Overlapping Intervals

L9 Hard Arrays & Hashing

Concept

Interval problems usually start by sorting by start time; then a careful merge walk keeps a live interval and extends it when the next one overlaps.

Given an array of intervals intervals where each is [start, end] (inclusive), merge all overlapping intervals and return the resulting array of non-overlapping intervals.

Examples

▸ intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

→ [[1, 6], [8, 10], [15, 18]]

▸ intervals = [[1, 4], [4, 5]]

→ [[1, 5]]

▸ intervals = []

→ []

Progressive Hints

Hint 1 · Nudge

Sort by start, then a new interval either stretches the current one or begins a new one.

Hint 2 · Plan

Sort the intervals by their start value. Keep the current interval; for each next interval, if its start is at or before the current end, extend the current end. Otherwise save the current interval and move to the next one.

Hint 3 · Approach

Sort by start. result = []. For each interval [s, e]: if result is empty or s exceeds the last interval's end, append [s, e]; otherwise set the last interval's end to the larger of the two ends. Return result.

Output

// Run your code to see the output here.