21. Merge Intervals

mediumAsked at Unity

Collapse overlapping time intervals into their union — exactly the pass Unity's physics engine runs to merge overlapping collider-wake windows before scheduling the fixed-update broadphase.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

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
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: [1,3] and [2,6] overlap and merge to [1,6].

Example 2

Input

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

Output

[[1,5]]

Approaches

1. Sort then linear scan

Sort by start time. Walk the sorted list; extend the current interval's end if the next start overlaps; otherwise push and advance.

Time: O(n log n)
Space: O(n)

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

Tradeoff:

Unity-specific tips

Unity expects you to drive to the sort-first insight unprompted. Describe the sorted list as a timeline of physics-event windows; once sorted, a single pointer is enough — no backtracking. State the sort cost explicitly; the interviewer will probe whether you know n log n dominates the linear merge.

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

Practice these live with InterviewChamp.AI →