Merge Intervals

Merge all overlapping intervals.

10 min read

Time: O(n)

Space: O(1)

Solve on LeetCode

Problem Understanding

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [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

Step 1 / 1

Initializing...

Custom Input

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

Dry Run

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

Step	Current	Result List	Action
Init	-	`[]`	Sort: `[[1,3], [2,6], [8,10], [15,18]]`
1	`[1,3]`	`[[1,3]]`	List empty. Add first interval.
2	`[2,6]`	`[[1,3]]`	`2 < 3` (Overlap). Merge! Result: `[[1,6]]`
3	`[8,10]`	`[[1,6]]`	`8 > 6` (No overlap). Add. Result: `[[1,6], [8,10]]`
4	`[15,18]`	`[[1,6], [8,10]]`	`15 > 10` (No overlap). Add. Result: `[[...], [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.

1def merge(intervals):
2    intervals.sort(key=lambda x: x[0])
3    merged = []
4    for interval in intervals:
5        if not merged or merged[-1][1] < interval[0]:
6            merged.append(interval)
7        else:
8            merged[-1][1] = max(merged[-1][1], interval[1])
9    return merged

Previous Problem

Search in Rotated Sorted Array

Next Problem

Insert Interval