Skip to main content

20. Merge Intervals

mediumAsked at Tesla

Collapse overlapping time intervals into a minimal set — Tesla's manufacturing scheduling systems use exactly this algorithm to consolidate overlapping production windows on the Fremont assembly line without leaving idle gaps.

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

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 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]]

Explanation: Intervals [1,3] and [2,6] overlap and are merged into [1,6].

Example 2

Input
intervals = [[1,4],[4,5]]
Output
[[1,5]]

Explanation: Touching intervals [1,4] and [4,5] are merged.

Approaches

1. Brute force pairwise check

Repeatedly scan for any overlapping pair and merge it; repeat until no overlaps remain. O(n^2) iterations.

Time
O(n^2)
Space
O(n)
function merge(intervals) {
  let changed = true;
  while (changed) {
    changed = false;
    intervals.sort((a, b) => a[0] - b[0]);
    for (let i = 0; i < intervals.length - 1; i++) {
      if (intervals[i][1] >= intervals[i + 1][0]) {
        intervals[i][1] = Math.max(intervals[i][1], intervals[i + 1][1]);
        intervals.splice(i + 1, 1);
        changed = true;
        break;
      }
    }
  }
  return intervals;
}

Tradeoff:

2. Sort then linear scan

Sort by start time; scan left to right and extend the current interval's end whenever the next interval overlaps. Single pass after sort.

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

Tradeoff:

Tesla-specific tips

Tesla interviewers connect this directly to production scheduling — Fremont runs 24/7 and overlapping maintenance windows must be merged to avoid halting the line twice. They grade on whether you sort by start time before scanning (many candidates forget) and on edge-case awareness: touching intervals that share a boundary should be merged. Follow-up: 'What if intervals can also be subtracted — find the gaps?' — think complement of the merged set.

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

Practice these live with InterviewChamp.AI →