24. Merge Intervals

mediumAsked at Meta

Collapse overlapping time windows into a minimal set — Meta's event-scheduling system, ad-slot deduplication, and calendar integrations all rely on this interval-merge pattern at their core.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

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, merged to [1,6].

Example 2

Input

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

Output

[[1,5]]

Explanation: Intervals touching at 4 are considered overlapping.

Approaches

1. Brute force (pairwise check)

For every pair of intervals check if they overlap and merge. Repeat until stable. Very slow — O(n^2) per pass.

Time: O(n^2)
Space: O(n)

function merge(intervals) {
  let changed = true;
  while (changed) {
    changed = false;
    const res = [];
    const used = new Array(intervals.length).fill(false);
    for (let i = 0; i < intervals.length; i++) {
      if (used[i]) continue;
      let [s, e] = intervals[i];
      for (let j = i+1; j < intervals.length; j++) {
        if (!used[j] && intervals[j][0] <= e) {
          e = Math.max(e, intervals[j][1]);
          used[j] = true; changed = true;
        }
      }
      res.push([s, e]);
    }
    intervals = res;
  }
  return intervals;
}

Tradeoff:

2. Sort then linear sweep

Sort by start time; walk the sorted list extending the current merged interval whenever the next start is at or before the current end. Single O(n) pass after sorting.

Time: O(n log n)
Space: O(n)

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = res[res.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      res.push(intervals[i]);
    }
  }
  return res;
}

Tradeoff:

Meta-specific tips

Meta commonly embeds merge-intervals inside a harder problem (like Meeting Rooms II or ad-auction scheduling). The key detail to catch: overlapping means start <= prev end, not start < prev end — adjacent intervals touching at a point are merged. State that out loud before coding; Meta interviewers note precision.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →