Example 1
ready- Input
intervals = [ [ 1, 3 ], [ 2, 6 ], [ 8, 10 ], [ 15, 18 ] ]- Expected
[ [ 1, 6 ], [ 8, 10 ], [ 15, 18 ] ]- Why
- the first two ranges overlap; the later two stay separate
Merge Intervals
35 min · merge()mediumOpen in LeetCode #56 ↗
A calendar export can describe one busy stretch with several overlapping blocks. Before you show it to a person, those fragments need to become one clean range.
Given an array intervals, where every entry is [start, end], combine all overlapping
intervals. Return the combined intervals sorted by ascending start.
Treat intervals as closed ranges: two intervals overlap when they share even one
endpoint. For example, [1, 4] and [4, 5] combine into [1, 5].
A few ground rules:
startis always less than or equal toend.- The input may arrive in any order and may contain duplicate intervals.
- Every covered point must appear in exactly one returned interval.
Constraints
1 <= intervals.length <= 100_000- Every interval has exactly two integers:
[start, end]. 0 <= start <= end <= 1_000_000_000
Hints
Find an ordering that helps
If intervals are sorted by start, any range that can extend the current merged range appears before a range that starts beyond it.
Keep one active range
Compare the next interval's start with the active range's end. If the start is no greater, extend the end when needed. Otherwise, the active range is finished.
Touching still counts
The overlap check is next_start <= current_end, not a strict comparison. Equality
means the intervals share an endpoint and must merge.
Follow-up
Could you describe which part of the algorithm proves that a finished interval can never overlap anything you haven't scanned yet?
Visible cases
Examples
Example 2
ready- Input
intervals = [ [ 1, 4 ], [ 4, 5 ] ]- Expected
[ [ 1, 5 ] ]- Why
- sharing endpoint 4 makes the two closed ranges overlap
Example 3
ready- Input
intervals = [ [ 5, 7 ], [ 1, 2 ], [ 2, 4 ] ]- Expected
[ [ 1, 4 ], [ 5, 7 ] ]- Why
- sorting exposes the touching chain from 1 through 4
Interview signal
Asked at
AmazonGoogleMetaBloomberg
Repeated pair merging
Start with copies of all intervals. Search for any overlapping pair, replace it with their combined range, and begin the search again. Once a full pass finds no pair, sort the survivors by start.
def merge(intervals: list[list[int]]) -> list[list[int]]:
work = [interval[:] for interval in intervals]
while True:
merged_a_pair = False
for i in range(len(work)):
for j in range(i + 1, len(work)):
left = max(work[i][0], work[j][0])
right = min(work[i][1], work[j][1])
if left <= right:
work[i] = [
min(work[i][0], work[j][0]),
max(work[i][1], work[j][1]),
]
work.pop(j)
merged_a_pair = True
break
if merged_a_pair:
break
if not merged_a_pair:
break
work.sort(key=lambda interval: interval[0])
return workOne search can inspect O(n²) pairs, and each successful search may remove only one interval. In the worst case that repeats O(n) times.
Time O(n³). Space O(n) for the working copy and result.
Sort + sweep
Sort by start, then carry one active merged range. When the next start is at most the active end, the ranges overlap; extend the end to the farther endpoint. When the next start is larger, no later interval can reach backward past it, so the active range is finished.
def merge(intervals: list[list[int]]) -> list[list[int]]:
ordered = sorted(intervals, key=lambda interval: interval[0])
merged = [ordered[0][:]]
for start, end in ordered[1:]:
current = merged[-1]
if start <= current[1]:
current[1] = max(current[1], end)
else:
merged.append([start, end])
return mergedSorting creates the guarantee the brute force was missing: once a gap appears, every later start lies even farther right.
Time O(n log n) for sorting, followed by one linear pass. Space O(n) for the sorted copy and returned intervals.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[
[
1,
6
],
[
8,
10
],
[
15,
18
]
]Run: visible + custom · Submit: full suite