Skip to main content

19. Merge Intervals

mediumAsked at Wise

Merge overlapping intervals into a minimal cover — Wise uses it as a stand-in for collapsing overlapping settlement windows in cross-border batches.

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

Problem

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the inputs.

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start <= end <= 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. Mark and rescan

Repeatedly find any overlapping pair and merge them until a pass finds none.

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

Tradeoff:

2. Sort then single-pass merge

Sort by start. Walk left-to-right and extend the current open interval when the next one overlaps, otherwise emit and reset.

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

Tradeoff:

Wise-specific tips

Wise grades whether you sort before scanning because their settlement windows can never be merged correctly without a deterministic order — they have seen candidates miss this and quietly emit overlapping batches.

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

Practice these live with InterviewChamp.AI →