Merge Intervals
Collapse a list of overlapping ranges into the smallest set of disjoint ones. The standard warm-up for sorting first and then sweeping once. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an array intervals where each element is [start, end] with start ≤ end. The intervals are in no particular order.
Merge every group of overlapping intervals into a single interval that covers the whole group, and return the result sorted by start. Two intervals overlap if they share at least one point, so [1, 4] and [4, 6] merge into [1, 6].
Example 1
- Input
- intervals = [[4, 7], [1, 3], [6, 10], [12, 14]]
- Output
- [[1, 3], [4, 10], [12, 14]]
[4, 7] and [6, 10] overlap on 6–7, so they become [4, 10]. The others stand alone.
Example 2
- Input
- intervals = [[2, 5], [5, 8]]
- Output
- [[2, 8]]
The intervals touch at 5, which counts as overlapping.
Example 3
- Input
- intervals = [[3, 20], [6, 9], [10, 11]]
- Output
- [[3, 20]]
Both smaller intervals sit entirely inside [3, 20].
Constraints
- 1 ≤ intervals.length ≤ 10⁴
- intervals[i].length = 2
- -10⁴ ≤ start ≤ end ≤ 10⁴
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Merge Intervals in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Merge Intervals
Pattern: Sort, then sweep
Overlap is hard to reason about when intervals arrive in random order: any interval might overlap any other, which points to comparing every pair. Sorting by start removes that problem. Once intervals are ordered by start, anything that overlaps the interval you're building must come right after it. If the next interval starts after your current end, nothing later can reach back either, because every later start is even larger.
So after sorting, one left-to-right pass is enough. Keep a "current" merged interval. If the next interval starts at or before the current end, extend the end to the larger of the two ends. Otherwise, close off the current interval and start a new one.
Approach 1: Repeated pairwise merging
Look for any two intervals that overlap, replace them with their union, and repeat until no pair overlaps. Easy to describe, but each round scans all pairs and there can be up to n rounds.
Time O(n³) naive, O(n²) with care · Space O(n)
Approach 2: Mark covered points
Since the coordinates are bounded, mark every covered point on a number line and read off the runs. This needs care to keep [1, 2] and [3, 4] separate (mark the gaps between points too), and it costs time and memory proportional to the coordinate range rather than n.
Time O(n · L + R) where L is interval length and R the range · Space O(R)
Approach 3: Sort by start and sweep
- Sort the intervals by start.
- Put the first interval in the result.
- For each following
[s, e]: ifs ≤ last.end, setlast.end = max(last.end, e). Otherwise append[s, e]as a new interval.
The max matters: an interval that starts inside the current one can end before it ([1, 10] then [2, 3]). Sorting dominates the cost; the sweep is linear.
Time O(n log n) · Space O(n) for the output (plus the sort)
| Approach | Time | Space |
|---|---|---|
| Repeated pairwise merging | O(n³) naive, O(n²) with care | O(n) |
| Mark covered points | O(n · L + R) where L is interval length and R the range | O(R) |
| Sort by start and sweep | O(n log n) | O(n) for the output (plus the sort) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Merge Intervals solution in Python
def merge(intervals: list[list[int]]) -> list[list[int]]:
merged: list[list[int]] = []
for start, end in sorted(intervals, key=lambda iv: iv[0]):
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedMerge Intervals solution in JavaScript
function merge(intervals) {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
const merged = [];
for (const [start, end] of sorted) {
const last = merged[merged.length - 1];
if (last && start <= last[1]) {
last[1] = Math.max(last[1], end);
} else {
merged.push([start, end]);
}
}
return merged;
}Common mistakes
- Setting the end to the next interval's end instead of the max, which shrinks `[1, 10]` to `[1, 3]` when `[2, 3]` follows.
- Using `<` instead of `≤` for the overlap test, so touching intervals like `[2, 5]` and `[5, 8]` stay separate.
- Forgetting to sort, or sorting by end instead of start.
- Appending a reference to an input interval and then mutating it, which silently changes the caller's data.
What interviewers look for
Ask early whether touching intervals count as overlapping; it changes one character of the code, and interviewers like seeing you nail down the definition. Then explain why sorting is enough: "after sorting by start, an interval can only overlap the one I'm currently building, never an earlier closed one." That one sentence is the proof of correctness.
Walk through a containment case like [1, 10], [2, 3] out loud before you finish. It is the case people most often get wrong.
Follow-up questions
How would you insert one new interval into a list that is already sorted and merged?
No sort is needed. Copy every interval that ends before the new one starts, then absorb every interval that overlaps it by widening its start and end, then copy the rest. That is a single O(n) pass.
What if intervals arrive one at a time and you need the merged set after each?
Keep the merged intervals in a balanced tree (or sorted container) keyed by start. For each new interval, find its neighbors with a binary search, merge with any it overlaps, and remove those. Each insert costs O(log n) plus the number of intervals it absorbs.
How would you find the maximum number of intervals that overlap at any point?
Turn each interval into a +1 event at its start and a -1 event just after its end, sort the events, and sweep while keeping a running sum. The largest running sum is the answer. This is the meeting-rooms problem.
Companies that ask Merge Intervals
Merge Intervals is tagged by 183 companies in our interview dataset. The score shows how often it comes up at each company.
- Tesla100%
- Grammarly100%
- Telstra100%
- Zepto100%
- Ripple100%
- Chewy100%
- Grubhub100%
- Tesco100%
- Dolby Laboratories98%
- Twitter97%
- Tenstorrent97%
- Zoominfo97%
- Nutanix96.1%
- Evertz95%
- Yelp94.2%
- IBM93.8%
- Wixcom93.1%
- Zoho92.9%
- The New York Times Company92%
- Walmart Labs91.3%
- Icertis90%
- Vertex Pharmaceuticals90%
- Ozon90%
- Godaddy89.3%
and 159 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required