Merge Intervals
A medium Intervals problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Intervals
- Sheets
- 3
- Core for
- 6 roles
- Platform
- LeetCode
The problem
Given an array of intervals where each interval has a start and end point, combine all overlapping or touching intervals into mutually disjoint intervals that cover the identical numbers.
Example 1
- Input
- intervals = [[1,3],[2,6],[8,10],[15,18]]
- Output
- [[1,6],[8,10],[15,18]]
- Why
- Intervals [1,3] and [2,6] share the range [2,3], merging into [1,6]. The remaining segments have no collisions.
Example 2
- Input
- intervals = [[1,4],[4,5]]
- Output
- [[1,5]]
- Why
- Intervals [1,4] and [4,5] touch at boundary 4, so they fuse into a single interval [1,5].
Constraints
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= intervals[i][0] <= intervals[i][1] <= 10^4
How to think about it
Updated 2026-09-09When intervals are sorted by their start points, all candidates that could possibly overlap with an active interval appear consecutively. One linear sweep comparing each candidate's start with the current running interval's finish suffices to either stretch the boundary or lock the interval and begin a fresh one.
Approaches, worst first
Graph connected components
time O(n^2) · space O(n^2)
Build an undirected graph where every interval represents a vertex, with edges between any two overlapping segments. Running breadth-first search identifies connected components and aggregates their extremes, but checking all pairs takes quadratic time.
Sort and linear scanWrite this one
time O(n log n) · space O(n)
Sort ascending by start coordinate. Seed the result with the first interval; for every subsequent interval, if its start is at most the last merged end, stretch that end to the maximum of both. Otherwise, push it as a distinct non-overlapping segment.
Where people lose marks · 3
- Overwriting the previous end with the current interval's end instead of taking the maximum, which shrinks the interval whenever an earlier segment completely envelops a later one like [1, 5] and [2, 3].
- Assuming boundary-touching intervals such as [1, 4] and [4, 5] remain disjoint; closed intervals that meet at a point must merge.
- Sorting by end coordinate instead of start coordinate, which breaks the property that subsequent intervals always start after prior ones.
Full solution
Sort by start and sweep once, stretching the running interval's end with max() whenever the next start falls at or before it. The graph/connected-components approach is O(n^2) and never worth writing here.
Python
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda iv: iv[0])
result: list[list[int]] = []
for start, end in intervals:
if result and start <= result[-1][1]:
result[-1][1] = max(result[-1][1], end)
else:
result.append([start, end])
return result
JavaScript
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const result = [];
for (const [start, end] of intervals) {
const last = result[result.length - 1];
if (last && start <= last[1]) {
last[1] = Math.max(last[1], end);
} else {
result.push([start, end]);
}
}
return result;
}
The theory behind it
Intervals — the ground this problem stands on. All Intervals problems
What Intervals is
An interval is a continuous range of numbers defined by two values: a start point and an end point. Think of a calendar event booked from two to four o'clock, or a cut segment on a ruler. Because each interval covers every number between its boundaries, two intervals can sit apart with empty room between them, touch at an edge, or overlap across a shared span of numbers.
When to reach for it
Reach for intervals when the input consists of start and end pairs representing time slots, schedules, ranges, or geometric segments. Phrasings asking to merge overlapping blocks, insert a new meeting into a busy calendar, find the minimum number of conference rooms needed, or count how many intervals must be removed to eliminate overlaps all point directly to interval patterns. Whenever problems involve resource contention over time, think intervals.
How the pattern works
The opening move is almost always sorting the intervals by their start times, or occasionally by their end times. Once ordered, compare the current interval with the previous one. If the new start time is less than or equal to the previous end time, the two intervals collide; merge them by stretching the previous end time to the maximum of both ends. If they do not collide, the previous interval is finished, so append it to the result and start tracking the new one. For room counts, split intervals into separate start and end events.
What each operation costs
| Operation | Time |
|---|---|
| sort intervals by start or end time | O(n log n) |
| merge sorted intervals in a single pass | O(n) |
| track active meetings using a min-heap | O(n log n) |
What usually goes wrong with Intervals
- Merging two overlapping intervals by taking the second interval end without using the maximum of both ends, which shrinks an interval when the first one completely swallowed the second.
- Treating intervals that touch at the exact same boundary point as disjoint when the problem statement defines boundaries as closed and inclusive.
- Forgetting to append the final merged interval to the output list after the iteration loop finishes.
Which roles need this problem
Intervals is a core topic for these 6 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 11 more roles, including Frontend Engineer, Full-Stack Developer, SDET / QA Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Intervals problems
Problem set and role mapping as of .