Pattern: Merge Intervals — Problem Statement & Solution Guide
Problem Description
You are provided with an array of intervals, where each interval is represented as a pair of integers [start, end] indicating a closed range [start, end]. Your task is to combine all overlapping intervals into a single continuous interval. Two intervals are considered overlapping if they share at least one common point, including cases where the end of one interval equals the start of another. The resulting array should contain only non-overlapping intervals, sorted in ascending order by their start values.
The input will be an array of arrays, where each inner array contains exactly two integers. The output must be an array of merged intervals, also represented as pairs of integers. If no intervals overlap, the output should be identical to the input (though sorted). The merging process must be efficient, handling large inputs within reasonable time complexity.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Pattern: Merge Intervals"
WHY DOES IT MATTER?
The merge‑intervals pattern teaches candidates how to transform a seemingly complex overlapping relationship into a simple linear process, a skill that generalizes to many interval‑based problems such as meeting room scheduling, video timeline stitching, and firewall rule consolidation.
OPTIMIZATION CHALLENGE
The key insight is that sorting eliminates the need for nested comparisons; once intervals are ordered, any overlap can only involve the current interval and the last merged interval, reducing the problem from O(n²) to O(n log n).
REAL-WORLD CONNECTION
Consider a distributed logging system where each server writes log files with timestamp ranges. To generate a continuous timeline for analysis, you must merge overlapping or adjacent timestamp intervals, analogous to consolidating shards in a distributed database to avoid duplicate data scans.
In an interview, sort in‑place if the language permits, then use a mutable list or stack to build the merged result—this avoids extra copying and keeps the code concise while still meeting the O(n) post‑sort scan requirement.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
Merging intervals is a classic example of a greedy algorithm that relies on sorting to impose a deterministic processing order. By sorting the intervals by their start coordinate, we guarantee that any potential overlap can only occur with the immediately preceding interval in the sorted list, allowing us to make a locally optimal decision—either extend the current merged interval or emit it and start a new one. This greedy choice is provably optimal because once intervals are ordered, any later interval cannot affect the decision made for earlier, non‑overlapping intervals, ensuring global optimality.
A naive solution would compare each interval with every other interval, leading to O(n²) time complexity, which quickly becomes infeasible for large datasets (e.g., millions of time‑range logs). The sorting step, which costs O(n log n), dominates the runtime but is dramatically faster than quadratic pairwise checks. After sorting, a single linear scan merges overlapping intervals in O(n) time, yielding an overall O(n log n) solution that scales well for production workloads.
The optimal paradigm thus combines two fundamental techniques: (1) a stable sort to linearize the problem space and (2) a greedy linear pass that maintains a running merged interval. This pattern appears in many domains—calendar scheduling, memory allocation, and range query optimization—making it a cornerstone of efficient interval handling in both algorithmic interviews and real‑world systems.
Interview Questions on This Problem
Q1How would you modify the merge intervals algorithm to also return the total length covered by the merged intervals?
After merging, iterate through the resulting list and sum up (end - start + 1) for each interval (or end - start for half‑open intervals). This adds O(k) time where k is the number of merged intervals, which is bounded by O(n).
Q2Given a stream of intervals arriving in real time, how can you maintain the merged set efficiently without re‑sorting the entire collection each time?
Use a balanced binary search tree (e.g., TreeMap) keyed by interval start. For each incoming interval, locate the predecessor and successor intervals, check for overlap, and merge accordingly, updating or deleting nodes as needed. Each insertion operates in O(log n) time, preserving near‑real‑time performance.
Q3Explain how the merge intervals problem relates to the problem of finding the union of multiple ranges in a distributed key‑value store.
In a distributed store, each node may hold a range of keys; merging overlapping key ranges ensures non‑redundant storage and simplifies range queries. The same sorting‑then‑linear‑scan technique can be applied to the list of node ranges to compute the global union, which is essential for load balancing and shard reallocation.
Examples
Input
[[1, 3], [2, 6], [8, 10], [15, 18]]
Output
[[1, 6], [8, 10], [15, 18]]
Explanation: Sort intervals by start: [[1,3], [2,6], [8,10], [15,18]]. Initialize result with [1,3]. Next interval [2,6] overlaps with [1,3] since 2 <= 3. Merge to [1,6]. Next interval [8,10] does not overlap with [1,6] since 8 > 6. Add [8,10] to result. Next interval [15,18] does not overlap with [8,10] since 15 > 10. Add [15,18] to result. Final output: [[1,6], [8,10], [15,18]].
Input
[[1, 4], [4, 5]]
Output
[[1, 5]]
Explanation: Sort intervals by start: [[1,4], [4,5]]. Initialize result with [1,4]. Next interval [4,5] overlaps with [1,4] since 4 <= 4 (touching endpoints count as overlap). Merge to [1,5]. No more intervals. Final output: [[1,5]].
Input
[[5, 6], [1, 2], [3, 4]]
Output
[[1, 2], [3, 4], [5, 6]]
Explanation: Sort intervals by start: [[1,2], [3,4], [5,6]]. Initialize result with [1,2]. Next interval [3,4] does not overlap with [1,2] since 3 > 2. Add [3,4] to result. Next interval [5,6] does not overlap with [3,4] since 5 > 4. Add [5,6] to result. Final output: [[1,2], [3,4], [5,6]].
Input
[[1, 10], [2, 3], [4, 5], [6, 7]]
Output
[[1, 10]]
Explanation: Sort intervals by start: [[1,10], [2,3], [4,5], [6,7]]. Initialize result with [1,10]. Next interval [2,3] overlaps with [1,10] since 2 <= 10. Merge to [1,10]. Next interval [4,5] overlaps with [1,10] since 4 <= 10. Merge to [1,10]. Next interval [6,7] overlaps with [1,10] since 6 <= 10. Merge to [1,10]. Final output: [[1,10]].
Constraints
- 1 <= intervals.length <= 10^5
- intervals[i].length == 2
- 0 <= intervals[i][0] <= intervals[i][1] <= 10^9
Optimal Approach & Strategy
Sort intervals by start, then perform a single linear scan merging overlapping or adjacent intervals on the fly.
Brute Force Approach
Compare every interval with every other interval and merge any that overlap, repeating until no more merges are possible.
Verified Code Solutions
function mergeIntervals(intervals) {
if (intervals.length === 0) {
return [];
}
intervals.sort((a, b) => a[0] - b[0]);
let result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= result[result.length - 1][1]) {
result[result.length - 1][1] = Math.max(result[result.length - 1][1], intervals[i][1]);
} else {
result.push(intervals[i]);
}
}
return result;
}class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return {};
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> result;
result.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] <= result.back()[1]) {
result.back()[1] = max(result.back()[1], intervals[i][1]);
} else {
result.push_back(intervals[i]);
}
}
return result;
}
}class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[][]{};
}
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> result = new ArrayList<>();
result.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= result.get(result.size() - 1)[1]) {
result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], intervals[i][1]);
} else {
result.add(intervals[i]);
}
}
return result.toArray(new int[result.size()][]);
}
}def mergeIntervals(intervals):
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
result = [intervals[0]]
for i in range(1, len(intervals)):
if intervals[i][0] <= result[-1][1]:
result[-1][1] = max(result[-1][1], intervals[i][1])
else:
result.append(intervals[i])
return resultfunction mergeIntervals(intervals) {
if (intervals.length === 0) {
return [];
}
intervals.sort((a, b) => a[0] - b[0]);
let result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= result[result.length - 1][1]) {
result[result.length - 1][1] = Math.max(result[result.length - 1][1], intervals[i][1]);
} else {
result.push(intervals[i]);
}
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.