Skip to main content

17. Merge Intervals

mediumAsked at Revolut

Merge overlapping intervals after sorting by start, a Revolut staple that mirrors collapsing overlapping authorization holds into a single net exposure window.

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 non-overlapping intervals that covers all the original input.

Constraints

  • 1 <= intervals.length <= 10^4
  • 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. Pairwise merge until stable

Repeatedly merge any overlapping pair found until none remain.

Time
O(n^2)
Space
O(n)
// while any overlapping pair (i,j) exists: replace with their union; restart scan

Tradeoff:

2. Sort by start then sweep

Sort by start; extend the last result if the current overlaps, else push as new. O(n log n).

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

Tradeoff:

Revolut-specific tips

Revolut frames this as collapsing pending auth holds — they care that you use `<=` (touching intervals merge) because two consecutive holds with no gap must net into one exposure block.

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

Practice these live with InterviewChamp.AI →