FAANGPrep Sprint

Merge Intervals

Merge all overlapping intervals.

Problem Understanding

Each intervals[i] is a range [start, end]. Combine every group of overlapping ranges into one range and return the result: a list in which no two ranges overlap and every original range is still covered.

Example:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] share the stretch from 2 to 3, so they become the single range [1,6].

Algorithm Strategy

Sort the Intervals: First, sort the intervals based on their start times. This brings potentially overlapping intervals next to each other.
Iterate and Merge: Create a merged list and add the first interval.
Compare: For each subsequent interval, check if it overlaps with the last interval in the merged list (i.e., current.start <= last.end).
Update: If they overlap, update the last interval's end time to max(last.end, current.end). If they don't, simply append the current interval to the merged list.

Interactive Visualization

4 INTERVALS

INPUT

intervals · as given

[1,3]

[2,6]

[8,10]

[15,18]

merged · 0

Read

—

Last end

—

Merged

merged

Empty

Merge 4 intervals

Sort by start — already in order: [[1,3], [2,6], [8,10], [15,18]]

Intervals

Legend & Complexity

The interval being merged, tagged “current”

The last interval in merged, tagged “last”, when it is compared

Already in merged: “appended” or “merged”

The returned intervals

Time

O(n log n)

Space

O(n)

Observe how sorting simplifies the problem to a linear merge process.

Dry Run

Input: [[1,3], [2,6], [8,10], [15,18]]

The code appends when merged is empty or its last interval ends before the current one starts (last end < start); otherwise it extends that last interval.

Step	Current	`last end < start`?	Action	merged
Init	-	-	Sort by start: `[[1,3], [2,6], [8,10], [15,18]]`	`[]`
1	`[1,3]`	merged is empty	Append	`[[1,3]]`
2	`[2,6]`	`3 < 2`? No — overlap	End = `max(3, 6) = 6`	`[[1,6]]`
3	`[8,10]`	`6 < 8`? Yes	Append	`[[1,6], [8,10]]`
4	`[15,18]`	`10 < 15`? Yes	Append	`[[1,6], [8,10], [15,18]]`

Edge Cases & Common Mistakes

Empty Input: Handle [] input gracefully.
Single Interval: Don't crash on inputs like [[1,4]].
Completely Contained: [[1,10], [2,5]] -> Merge logic max(10, 5) = 10 handles this.
Touching: [[1,2], [2,3]] -> 2 <= 2, so they merge into [1,3].

Solution

Optimal solution using O(N log N) sorting.

Merge Intervals Code

1var merge = function(intervals) {
2    intervals.sort((a, b) => a[0] - b[0]);
3    const merged = [];
4    for (const interval of intervals) {
5        if (!merged.length || merged[merged.length - 1][1] < interval[0]) {
6            merged.push(interval);
7        } else {
8            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
9        }
10    }
11    return merged;
12};

Previous Problem

Search in Rotated Sorted Array

Next Problem

Insert Interval