Skip to main content

56. Merge Intervals

mediumAsked at GoDaddy

Merge all overlapping intervals into the minimum non-overlapping set — GoDaddy's SRE team applies this pattern to consolidate maintenance windows and detect scheduling conflicts across their global hosting infrastructure.

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, merged to [1,6].

Example 2

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

Approaches

1. Brute force

Repeatedly scan the list and merge any pair that overlaps until no more merges occur.

Time
O(n^2)
Space
O(n)
function merge(intervals) {
  let merged = true;
  let arr = intervals.map(i => [...i]);
  while (merged) {
    merged = false;
    const result = [];
    const used = new Array(arr.length).fill(false);
    for (let i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      let cur = [...arr[i]];
      for (let j = i + 1; j < arr.length; j++) {
        if (used[j]) continue;
        if (arr[j][0] <= cur[1]) {
          cur[1] = Math.max(cur[1], arr[j][1]);
          used[j] = true;
          merged = true;
        }
      }
      result.push(cur);
    }
    arr = result;
  }
  return arr;
}

Tradeoff:

2. Sort then linear scan

Sort by start time; one linear pass merges any interval whose start falls within the last merged interval's end.

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:

GoDaddy-specific tips

GoDaddy's SRE interviews expect you to state why sorting is the prerequisite — without it, a single-pass merge silently misses non-adjacent overlaps. They also look for candidates who can extend this to 'insert interval' (LC 57) in O(n) without re-sorting, which mirrors their online scheduling system.

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

Practice these live with InterviewChamp.AI →