Merging intervals
In one line
Sort intervals by start, then sweep once: each interval either extends the last merged block or starts a new one, for O(n log n) total.
What it is
Merging intervals means combining every group of overlapping intervals into one interval, so the output is a sorted list of disjoint ranges that covers exactly the same points as the input.
The trick is sorting by start time. After sorting, an interval can only overlap the block you are currently building (the last one in the output), never an older one, so a single pass is enough.
Why interviewers ask
Merge Intervals is one of the most frequently asked interview problems and a building block for many others: free time, total covered length, calendar union, inserting into a schedule. It tests sorting by a key, an in-place update of the last element, and edge cases like nested and touching intervals.
How it works
- 1Sort the intervals by start.
- 2Start an empty output list.
- 3For each interval: if the output is empty or the interval starts after the last block ends, append it as a new block.
- 4Otherwise it overlaps the last block, so set the last block's end to max(last end, this end). Using max matters for nested intervals like [1, 10] then [2, 3].
- 5The output is sorted and disjoint. Sorting costs O(n log n) and the sweep costs O(n).
Worked example · merge([[1, 3], [8, 10], [2, 6], [15, 18]])
- Sort by start: [1, 3], [2, 6], [8, 10], [15, 18].
- [1, 3]: output is empty, so output = [[1, 3]].
- [2, 6]: 2 <= 3, overlaps. Last end = max(3, 6) = 6. Output = [[1, 6]].
- [8, 10]: 8 > 6, new block. Output = [[1, 6], [8, 10]].
- [15, 18]: 15 > 10, new block. Output = [[1, 6], [8, 10], [15, 18]].
Picture it
Painting stripes on a fence from a list of jobs. Sort the jobs by where they start; as you walk along, each new job either continues the wet stripe you are on or starts a new stripe further down.
Reference code
def merge(intervals):
intervals = sorted(intervals, key=lambda x: x[0])
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
# overlaps the last block: extend it if needed
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
print(merge([[1, 3], [8, 10], [2, 6], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]Only the last merged block can overlap the current interval because everything is sorted by start. max() handles nested intervals. Change start <= to start < if touching intervals should stay separate.
Key patterns
Sort and sweep
When: Merge any list of intervals
How: Sort by start, compare each interval only with the last merged block.
Total covered length
When: How much time or space is covered
How: Merge first, then sum end - start of each block.
Gaps between blocks
When: Free time, missing ranges
How: After merging, each gap is [block[k].end, block[k + 1].start].
Merge as a cleanup step
When: Before other interval logic
How: Normalising to sorted, disjoint intervals simplifies insert, search and intersection.
Real-world use
Calendar busy blocks
Free/busy views merge a person's overlapping events into busy blocks, so 9:00-10:00 and 9:30-11:00 show as one busy period from 9:00 to 11:00.
Genomic region merging
bedtools merge combines overlapping genomic features into single regions, a standard step in sequencing pipelines.
Download and cache segments
Download managers and video caches that fetch byte ranges out of order merge received ranges to know which parts of a file are complete and which gaps to request.
Uptime and incident reporting
Monitoring tools merge overlapping outage windows from many alerts before computing total downtime, so the same minute is not counted twice.
In a project
An SRE team wants the true monthly downtime of a service, but alerts from 5 regions and several checks overlap heavily.
- Export every alert as [start_time, end_time] in UTC.
- Sort by start and merge overlapping windows with the one-pass sweep.
- Sum end - start over the merged blocks to get total downtime, and list the blocks as distinct incidents.
- Compare total downtime with the SLA budget (for example 43.8 minutes a month for 99.9%).
Impact: The reported downtime stops being inflated by double-counted alerts, so SLA reports to customers become accurate, and the merged incidents give a clean timeline for postmortems.
Trade-offs
Use it when
- You need disjoint ranges covering the same points
- Computing coverage, gaps or unions
- Intervals arrive in a batch and can be sorted
Avoid it when
- Intervals arrive one at a time and you must keep the merged set up to date: use a balanced tree or sorted container keyed by start
- You need to keep the original intervals' identities (merging loses them)
Cost: O(n log n) time for the sort plus O(n) for the sweep; O(n) space for the output (O(log n) to O(n) extra for the sort).
Common mistakes
- Forgetting to sort first.
- Setting the end to the current interval's end instead of max(last end, current end), which breaks nested intervals like [1, 10], [2, 3].
- Comparing each interval with the previous input interval instead of the last merged block.
- Not clarifying whether [1, 2] and [2, 3] should merge.
- Mutating the caller's input list without saying so.
Interview questions
Quick revision
- Sort by start.
- If start <= last.end: last.end = max(last.end, end).
- Else append a new block.
- Only compare with the last merged block.
- Time O(n log n), sweep O(n).
- Coverage = sum of merged lengths; gaps = between blocks.
Check yourself
1. What does merge([[1, 4], [2, 3]]) return?
2. Why sort by start before merging?
3. What does merge([[1, 2], [2, 3]]) return using start <= last end?
4. What is the time complexity of merging n unsorted intervals?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.