Skip to main content

56. Merge Intervals

mediumAsked at Cisco

Merge Intervals at Cisco appears in any interview involving scheduling, packet timing windows, or maintenance ticket consolidation. The interviewer is checking whether you sort first and whether you mutate the last merged interval in-place rather than building fresh objects each step.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-II onsite reports list Merge Intervals as a 30-minute coding round.
  • Blind (2025-10)— Cisco interview thread cites this as a recurring problem for backend roles.

Problem

Given an array of intervals where intervals[i] = [starti, endi], 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 <= starti <= endi <= 10^4

Examples

Example 1

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

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

Example 2

Input
intervals = [[1,4],[4,5]]
Output
[[1,5]]

Explanation: Touching intervals are considered overlapping.

Approaches

1. Brute-force: pairwise check until no merges happen

Repeatedly scan all pairs (i, j) and merge any overlap. Stop when a full pass produces no merges.

Time
O(n^3)
Space
O(n)
function mergeBrute(intervals) {
  const result = intervals.map(i => [...i]);
  let changed = true;
  while (changed) {
    changed = false;
    for (let i = 0; i < result.length; i++) {
      for (let j = i + 1; j < result.length; j++) {
        if (result[i][0] <= result[j][1] && result[j][0] <= result[i][1]) {
          result[i] = [Math.min(result[i][0], result[j][0]), Math.max(result[i][1], result[j][1])];
          result.splice(j, 1);
          changed = true;
          break;
        }
      }
      if (changed) break;
    }
  }
  return result;
}

Tradeoff: Quadratic just on the overlap scan plus an outer 'until stable' loop. Useful only as a starting point on the whiteboard — Cisco interviewers will push you to sort immediately.

2. Sort + linear scan (optimal)

Sort by start. Walk the array. If the current interval's start <= the last merged interval's end, extend the end; otherwise push a new interval.

Time
O(n log n)
Space
O(n)
function merge(intervals) {
  if (intervals.length <= 1) return intervals;
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [intervals[0].slice()];
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const [s, e] = intervals[i];
    if (s <= last[1]) {
      last[1] = Math.max(last[1], e);
    } else {
      result.push([s, e]);
    }
  }
  return result;
}

Tradeoff: The canonical answer. Sorting dominates at O(n log n); the merge pass is O(n). The 'mutate last in-place' line is what makes this O(n) extra space rather than O(n^2).

Cisco-specific tips

Cisco interviewers want you to ASK whether 'overlapping' includes touching. The standard answer is yes — [1,4] and [4,5] merge into [1,5]. Once that's clarified, the sort + scan pattern is mechanical. Where candidates lose points is on the comparator — sorting by end instead of start breaks the invariant and you'll merge incorrectly. State out loud: 'I sort by start so that I only ever need to look backward at the last merged interval.'

Common mistakes

  • Sorting by end instead of start — breaks the 'last merged' invariant because you can't tell which intervals you'd touch.
  • Using `>` instead of `<=` on the overlap check, missing the touching-intervals case ([1,4] + [4,5]).
  • Pushing a fresh `[s, e]` for the first interval, then forgetting that subsequent merges should mutate `last` — wastes space.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

  • Insert Interval (LC 57) — given sorted non-overlapping intervals, insert a new one and re-merge.
  • Non-overlapping Intervals (LC 435) — minimum removals to make non-overlapping.
  • Meeting Rooms II (LC 253) — minimum number of rooms / number of overlapping intervals at peak.
  • Find First and Last Position (LC 34) — bonus binary-search variant if interviewer pivots.

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 sort by start specifically?

Because the merge invariant is 'the next interval can only overlap with the LAST merged interval' — by start-time ordering, anything to the left of the current interval is already merged. Sorting by end breaks that invariant: an interval ending at time T might overlap with something starting at time T-1 that you haven't seen yet.

Is the touching case (end == start) really an overlap?

By LeetCode convention yes, but the interviewer ALWAYS expects you to ask. In real Cisco scheduling work, a maintenance window ending at 14:00 and another starting at 14:00 might be 'back to back, not overlapping' depending on the team. 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 Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →