Skip to main content

20. Merge Intervals

mediumAsked at Klarna

Merge all overlapping intervals into a minimal disjoint set.

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 input intervals.

Constraints

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

Loop merging any overlapping pair found, until no more merges are possible.

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

Tradeoff:

2. Sort by start, sweep

Sort intervals by start time, then sweep and extend the most recent interval whenever the next one overlaps; otherwise push a new interval.

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];
    if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]);
    else out.push(intervals[i].slice());
  }
  return out;
}

Tradeoff:

Klarna-specific tips

Klarna's merchant-settlement engine literally runs this sweep to collapse payout windows; they will grade you on whether you handle touching-but-not-overlapping intervals consistently with their billing semantics.

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

Practice these live with InterviewChamp.AI →