Skip to main content

52. Merge Intervals

mediumAsked at Ola

Merge a collection of overlapping intervals.

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 intervals in the 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. Sweep with set of seconds

Mark covered seconds in a set or array; reconstruct contiguous runs.

Time
O(max - min)
Space
O(max - min)
// boolean array across full range, scan for runs; bad if values are sparse

Tradeoff:

2. Sort and merge

Sort by start; walk and extend the current interval when the next one overlaps.

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

Tradeoff:

Ola-specific tips

Ola asks merge-intervals to gauge classic interval discipline; tie it to compacting overlapping driver shift availability windows before allocation.

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

Practice these live with InterviewChamp.AI →