Skip to main content

56. Merge Intervals

mediumAsked at Anduril

Merge all overlapping intervals in a list. Anduril asks this because interval merging is a real problem in mission scheduling and time-window conflict resolution for autonomous systems — you need to sort, then reason carefully about edge cases where intervals share an endpoint.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2026-Q1)— Listed in Anduril SWE onsite reports as an interval-reasoning medium question.
  • Blind (2025-11)— Anduril candidate threads cite Merge Intervals as a sorting + greedy medium that appears across multiple interview rounds.

Problem

Given an array of intervals where intervals[i] = [starti, endi], 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 <= starti <= endi <= 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]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping (shared endpoint).

Approaches

1. Sort then linear scan

Sort intervals by start time. Walk the sorted list; if the current interval overlaps with the last merged interval, extend it. Otherwise, push a new interval.

Time
O(n log n)
Space
O(n)
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    const curr = intervals[i];
    if (curr[0] <= last[1]) {
      // Overlapping: extend the last interval's end
      last[1] = Math.max(last[1], curr[1]);
    } else {
      merged.push(curr);
    }
  }
  return merged;
}

Tradeoff: O(n log n) for sort, O(n) linear scan. The overlap condition is curr[0] <= last[1] — not strictly less than, so touching endpoints (like [1,4] and [4,5]) are merged. This subtlety is a common miss.

Anduril-specific tips

State the sort invariant before coding: 'After sorting by start time, if two intervals overlap, the one with the smaller start can only be followed by an overlapping interval, not preceded by one.' At Anduril, mention the touching-endpoints edge case ([1,4]+[4,5] → [1,5]) — it signals attention to boundary conditions that matter in time-critical scheduling. Also mention when you'd use this in practice: mission deconfliction, sensor window merging.

Common mistakes

  • Using curr[0] < last[1] instead of curr[0] <= last[1] — misses the touching-endpoint case.
  • Not taking Math.max when extending — if curr is fully contained within last, you'd incorrectly shrink last's end.
  • Modifying the input sort order in place when the caller expects the original array unchanged — document the side effect.
  • Forgetting to seed merged with intervals[0] before the loop — the loop starts at index 1.

Follow-up questions

An interviewer at Anduril may pivot to one of these next:

  • Insert Interval (LC 57) — given a set of non-overlapping intervals, insert a new one and merge.
  • Minimum number of meeting rooms required (LC 253).
  • How would you merge intervals arriving as a real-time stream?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why sort by start time?

After sorting, all potential overlap partners for interval i are immediately to its right. Without sorting, you'd need O(n^2) comparisons.

Why Math.max when merging ends?

The current interval might be fully contained within the last merged interval. Without max, you'd shrink the end incorrectly.

What if the input has only one interval?

merged is seeded with that interval, the loop body never executes, and merged is returned as-is.

Practice these live with InterviewChamp.AI

Drill Merge Intervals and other Anduril interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →