Skip to main content

16. Merge Intervals

mediumAsked at ByteDance

Merge overlapping intervals into a minimal set — ByteDance uses it to test sort + sweep reasoning before scaling to watch-time aggregation problems.

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

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. Boolean mark line

Paint every covered minute on a boolean array, then re-scan to extract intervals.

Time
O(n + R)
Space
O(R)
// paint covered range, then walk array to extract runs

Tradeoff:

2. Sort by start then sweep

Sort intervals by start. Walk through; if the next interval overlaps the last merged one, extend it, else push a new merged interval.

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

Tradeoff:

ByteDance-specific tips

ByteDance interviewers want the equality case [1,4] [4,5] resolved up front, mirroring how their watch-time aggregator team enforces inclusive-end conventions across services.

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

Practice these live with InterviewChamp.AI →