56. Merge Intervals
mediumAsked at IBMMerge Intervals is IBM's sort-then-sweep screener — directly relevant to calendar scheduling and time-range queries in IBM Cloud monitoring. The interviewer is grading whether you sort by start, whether you handle the touching-but-not-overlapping edge case, and whether you ship O(n log n) cleanly.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in IBM loops.
- Glassdoor (2026-Q1)— IBM SWE-2 / SWE-3 onsite recurring problem (intervals/sweep track).
- LeetCode (2026-Q1)— Top-30 IBM-tagged problem (medium tier).
- GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive.
Problem
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Constraints
1 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^4
Examples
Example 1
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2
intervals = [[1,4],[4,5]][[1,5]]Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Approaches
1. Sort by start, then sweep (optimal)
Sort intervals by start. Walk through; if the current interval's start <= the previous result's end, extend; otherwise push as new.
- Time
- O(n log n)
- Space
- O(n) for output (or O(1) if mutating in place)
function merge(intervals) {
if (intervals.length === 0) return [];
intervals.sort((a, b) => a[0] - b[0]);
const out = [intervals[0].slice()];
for (let i = 1; i < intervals.length; i++) {
const last = out[out.length - 1];
const [s, e] = intervals[i];
if (s <= last[1]) {
if (e > last[1]) last[1] = e;
} else {
out.push([s, e]);
}
}
return out;
}Tradeoff: Canonical answer. Sort dominates the complexity. The `s <= last[1]` check is what defines 'touching counts as overlapping' — if the problem said strict overlap, you'd use `<` instead. Always confirm this with the interviewer.
2. Connected-components on graph
Build a graph where two intervals are connected if they overlap. Find connected components; merge each component.
- Time
- O(n^2)
- Space
- O(n^2)
function mergeGraph(intervals) {
const n = intervals.length;
const adj = Array.from({ length: n }, () => []);
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const overlap = intervals[i][0] <= intervals[j][1] && intervals[j][0] <= intervals[i][1];
if (overlap) {
adj[i].push(j);
adj[j].push(i);
}
}
}
const visited = new Array(n).fill(false);
const out = [];
for (let i = 0; i < n; i++) {
if (visited[i]) continue;
const comp = [];
const stack = [i];
while (stack.length > 0) {
const node = stack.pop();
if (visited[node]) continue;
visited[node] = true;
comp.push(node);
for (const next of adj[node]) {
if (!visited[next]) stack.push(next);
}
}
let lo = Infinity;
let hi = -Infinity;
for (const idx of comp) {
if (intervals[idx][0] < lo) lo = intervals[idx][0];
if (intervals[idx][1] > hi) hi = intervals[idx][1];
}
out.push([lo, hi]);
}
return out.sort((a, b) => a[0] - b[0]);
}Tradeoff: Strictly worse than sort-and-sweep but useful as a follow-up when the interviewer pivots to 'what if the data is distributed and you can't sort?' Connected-components scales horizontally on a graph cluster. Mention it; don't ship it.
IBM-specific tips
IBM Cloud monitoring and Watson scheduling interviewers grade this on whether you ALWAYS confirm the spec's overlap definition first: 'do touching intervals (e.g., [1,4] and [4,5]) merge?' The LeetCode answer is yes, but the question is real for calendar / time-range systems. Stating this clarifying question aloud earns the rubric checkbox. Then the sweep is mechanical; the discipline is in the spec confirmation.
Common mistakes
- Sorting by end instead of start — produces a different result (and is wrong for this problem; right for some interval-scheduling variants).
- Using `<` instead of `<=` for the overlap check — fails the touching-intervals case.
- Mutating the input array via `out[out.length - 1] = intervals[i]` instead of `last[1] = max(last[1], e)` — loses the start of the merged group.
- Forgetting to handle the empty input array — `intervals[0]` throws.
- Using `.slice()` once and assuming it's enough — if you mutate `last` later, you must ensure each pushed interval is a fresh copy.
Follow-up questions
An interviewer at IBM may pivot to one of these next:
- Insert Interval (LeetCode 57) — insert a new interval and merge.
- Meeting Rooms II (LeetCode 253) — count overlapping intervals at any point.
- What if the input is streaming and you must merge online? (Use a balanced BST or interval tree.)
- Employee Free Time (LeetCode 759) — complement of merged intervals.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does sorting matter?
Sorted by start, a single linear sweep suffices because each new interval only needs to be compared with the LAST emitted result. Without sorting, you'd have to compare every pair (O(n^2)). The sort is what makes the sweep work in one pass.
Do touching intervals like [1,4] and [4,5] merge?
Yes per the LeetCode spec. The example explicitly states they merge to [1,5]. In real calendar systems, the answer can vary — always clarify with the interviewer before coding. State the assumption out loud.
Free learning resources
Curated free links for this problem.