Skip to main content

20. Merge Intervals

mediumAsked at Ramp

Collapse a list of intervals into the minimum set of non-overlapping intervals.

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

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]]

Example 2

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

Approaches

1. Brute force

Repeatedly scan for any overlapping pair and merge until no merges remain.

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

Tradeoff:

2. Sort by start then sweep

Sort intervals by start. Walk left-to-right; extend the last result interval when the next start lies inside it, otherwise push a new interval.

Time
O(n log n)
Space
O(n)
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const [s, e] of intervals) {
    if (out.length && out[out.length - 1][1] >= s) {
      out[out.length - 1][1] = Math.max(out[out.length - 1][1], e);
    } else {
      out.push([s, e]);
    }
  }
  return out;
}

Tradeoff:

Ramp-specific tips

Ramp uses interval merging to collapse overlapping spend-policy windows in their rules engine — sort-then-sweep is the canonical answer and they grade for noticing the sort cost dominates.

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

Practice these live with InterviewChamp.AI →