Skip to main content

56. Merge Intervals

mediumAsked at Microsoft

Merge Intervals is the Microsoft sort-then-sweep classic. Sort intervals by start, then walk left to right merging into the previous interval whenever the current start is <= previous end. The interviewer wants you to name 'sort plus single pass' as the structure before coding.

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

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Azure org onsite reports list Merge Intervals as the most-repeated interval-sweep medium.
  • Levels.fyi (2026-Q1)— Microsoft L60/L61 interview compilations repeatedly include Merge Intervals.

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, single pass merge (optimal)

Sort intervals by start. Walk left to right: if the current start is <= the last merged interval's end, extend that end; otherwise append the current interval as a new merge group.

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

Tradeoff: Sort dominates at O(n log n); the merge pass is O(n). Microsoft loves this question because the structure (sort + sweep) generalizes to dozens of interval problems.

2. Brute-force pairwise merge

Repeatedly find any overlapping pair and merge them. Stop when no pair overlaps.

Time
O(n^3) worst case
Space
O(n)
function merge(intervals) {
  let result = intervals.map(x => x.slice());
  let changed = true;
  while (changed) {
    changed = false;
    outer:
    for (let i = 0; i < result.length; i++) {
      for (let j = i + 1; j < result.length; j++) {
        if (result[i][1] >= result[j][0] && result[j][1] >= result[i][0]) {
          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 outer;
        }
      }
    }
  }
  return result;
}

Tradeoff: Cubic. Worth mentioning to acknowledge you considered it, then explicitly rejecting in favor of the sort approach. Microsoft graders want the verbal rejection more than the implementation.

Microsoft-specific tips

Microsoft is grading whether you recognize the sort-then-sweep pattern. Name it explicitly: 'sort by start, then a single linear pass merges anything overlapping with the last accepted interval.' Edge case to call out: [1,4],[4,5] DOES merge to [1,5] because touching endpoints overlap per the problem statement — verifying this with the interviewer earns reliability points.

Common mistakes

  • Using strict < instead of <= in the overlap check — fails the touching-endpoint case.
  • Modifying the input array unintentionally (forgetting to copy intervals[i] before pushing).
  • Not sorting first and trying to merge in the original order — fails on [[2,3],[1,4]].

Follow-up questions

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

  • Insert Interval (LC 57) — input already sorted; do it in O(n).
  • Non-overlapping Intervals (LC 435) — count min removals to leave a non-overlapping set.
  • Meeting Rooms II (LC 253) — min rooms = max overlap count, sweep-line variant.

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 and not by end?

Sorting by start gives you the invariant that everything to the left of i has been processed; you only need to compare to the last merged interval. Sort-by-end works too but the merge condition gets fiddlier.

Are touching intervals considered overlapping?

Per LeetCode 56, yes — [1,4] and [4,5] merge to [1,5]. Always confirm this with the interviewer; some variants use strict overlap.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →