Skip to main content

21. Merge Intervals

mediumAsked at MercadoLibre

Merge overlapping intervals into the smallest set of non-overlapping ranges.

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

Repeatedly scan the list and merge any pair that overlaps until no overlaps remain.

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[i][0] <= intervals[j][1]) {
        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 + sweep

Sort by start, then sweep once and either extend the last merged interval or push a new one.

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

Tradeoff:

MercadoLibre-specific tips

Mercado Pago risk engineers ask this because suspicious transaction windows get merged the same way — overlapping fraud signals collapse into a single review interval before being routed to analysts.

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

Practice these live with InterviewChamp.AI →