Skip to main content

56. Merge Intervals

mediumAsked at IBM

Merge 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 Alex Chen, 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^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4

Examples

Example 1

Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]

Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2

Input
intervals = [[1,4],[4,5]]
Output
[[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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Merge Intervals and other IBM interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →