25. Merge Intervals

mediumAsked at Box

Collapse overlapping time ranges into a minimal set — Box applies this exact algorithm when computing consolidated file-lock windows and audit-trail time ranges across concurrent enterprise users.

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

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: Intervals [1,3] and [2,6] overlap and merge 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. Brute force — repeated scan

Repeatedly scan all pairs and merge any overlapping pair until no merges remain. Very slow for large inputs.

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

function merge(intervals) {
  let changed = true;
  while (changed) {
    changed = false;
    const next = [];
    let i = 0;
    while (i < intervals.length) {
      let [s, e] = intervals[i];
      let j = i + 1;
      while (j < intervals.length && intervals[j][0] <= e) {
        e = Math.max(e, intervals[j][1]);
        j++;
        changed = true;
      }
      next.push([s, e]);
      i = j;
    }
    intervals = next;
  }
  return intervals;
}

Tradeoff:

2. Optimal — sort then linear merge

Sort by start time; walk the sorted list and either extend the current interval's end or push a new one. Single pass after sort.

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

function merge(intervals) {
  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:

Box-specific tips

Box interviewers often extend this to 'Insert Interval' (LC 57) — be ready to handle the case where a new lock window must be inserted into an already-merged list without full re-sort. Also, when discussing the sort step, note that Box's file-versioning system stores events pre-sorted by timestamp, making the sort O(1) in practice and the overall algorithm O(n).

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 Box interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →