Merge Intervals
Combine every group of overlapping ranges into one, and see why sorting by start is what removes the inner loop
Problem Statement
Given a list of intervals, merge all overlapping ones and return the non-overlapping intervals that cover the same total range.
Input: [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
[1,3] and [2,6] overlap, so they become [1,6]
Input: [[1,4], [4,5]]
Output: [[1,5]]
touching counts as overlapping hereIntuition
The naive approach: compare every interval against every other, merge any pair that overlaps, and repeat until nothing changes. That is O(n²) at best — and merging can create new overlaps, so it may need several passes.
[[1,3], [8,10], [2,6]]
pass 1: [1,3] vs [8,10] → no
[1,3] vs [2,6] → merge → [1,6]
pass 2: must re-check everything, because [1,6] is newThe trouble is that an overlapping partner could be anywhere in the list, so nothing can ever be finalised.
The insight
Sort by start time. Now anything overlapping the current interval must be the very next one.
Why: after sorting, every later interval starts at or after the current one. If the next interval starts beyond the current end, so does every interval after it — they start even later. Nothing further along can reach back.
So the moment one interval fails to overlap, the current one is finished forever. One pass, no re-checking.
That is the whole problem. Sorting costs O(n log n) and buys the ability to close an interval permanently.
Approach
Sort by start time
intervals.sort(key=lambda x: x[0]). This is the step that makes everything else valid.
Hold one interval open
Take the first as current. It is not finished — a later interval may extend it.
For each remaining interval, overlap or not?
Overlaps (next.start <= current.end) → extend: current.end = max(current.end, next.end).
Does not overlap → current can never grow again. Output it, and make next the new current.
Output the last one
The loop ends with current still open. Nothing inside the loop will close it.
The containment case is where `max` earns its place
[[1, 10], [2, 3]]
with max: end = max(10, 3) = 10 → [1,10] ✓
without max: end = 3 → [1,3] ✗ lost 3..10[2, 3] sits entirely inside [1, 10]. Sorting by start puts it second, so a naive current.end = next.end shrinks the answer.
This passes most casual tests and fails the moment one interval contains another.
Solution
def merge(intervals: list[list[int]]) -> list[list[int]]:
"""Merge all overlapping intervals.
Sorting by start guarantees that any overlapping interval is the
next one, so a single pass suffices.
"""
if not intervals:
return []
intervals.sort(key=lambda interval: interval[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
# Overlap — widen the interval already in the output.
merged[-1][1] = max(last_end, end)
else:
merged.append([start, end])
return mergedWriting into merged[-1] instead of a separate current variable removes the "don't forget the last one" step entirely — the open interval is always the final element of the output.
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(n)
Time — dominated by the sort. The merge pass itself is O(n), so you cannot do better without a sorted input; comparison sorting is the floor.
Space — O(n) for the output. The sort adds O(log n) for Python's Timsort or O(n) depending on the engine; if modifying the input is allowed, no additional structure is needed.
Edge Cases
Related Problems
- Insert Interval — the same merge, on an input that is already sorted
- Non-overlapping Intervals — sorted by end instead, and greedy
- Intervals — the overlap test and why sorting is the key step