56. Merge Intervals

Q: Why does sorting by start time work?

After sorting, overlapping intervals are always adjacent. You can never have an interval at index i that overlaps with index i+2 but not i+1, because that would mean i+1 starts between i and i+2 — which would itself overlap with both.

Q: What if two intervals share only a single endpoint (e.g., [1,3] and [3,5])?

By convention (and the problem spec), touching at an endpoint counts as overlapping → merge to [1,5]. The condition curr[0] <= last[1] handles this.

Q: Can you do this without sorting?

Not in general. An O(n log n) lower bound applies because you can sort n numbers in O(n) calls to a merge-intervals oracle. The sort is necessary.

mediumAsked at Citadel

Interval merging is a direct analog of consolidating overlapping trading windows, computing continuous market hours, or merging order-book time slots. Citadel uses this problem to test sort-first reasoning and the ability to handle all overlap cases correctly — especially the 'contained within' edge case.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

Glassdoor (2026-Q1)— Citadel SWE interview reports list Merge Intervals as a canonical problem for testing interval-manipulation and sort-based reasoning.
Blind (2025-10)— Citadel candidates note interval problems appear frequently because of their direct applicability to trading time windows and scheduling.

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

Example 2

Input

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

Output

[[1,5]]

Explanation: Touching at endpoint 4 — considered overlapping.

Approaches

1. Sort by start + linear scan

Sort intervals by start time. Iterate and either merge the current interval into the last result (if overlapping) or append it as a new non-overlapping interval.

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

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];
    const curr = intervals[i];
    if (curr[0] <= last[1]) {
      // Overlapping: extend the last interval's end if needed
      last[1] = Math.max(last[1], curr[1]);
    } else {
      // Non-overlapping: append as new interval
      result.push(curr);
    }
  }
  return result;
}

Tradeoff: O(n log n) dominated by the sort. After sorting, the linear scan is O(n). The Math.max(last[1], curr[1]) handles the 'contained within' case (e.g., [1,10] + [2,5] → [1,10]) correctly. This is the canonical answer.

Citadel-specific tips

State sort-first reasoning explicitly: 'Once sorted by start time, any overlapping interval must have start ≤ previous end. I only need to look at the last merged interval.' Draw all three overlap cases on your whiteboard: partial overlap, full containment, and touch-at-endpoint. The touch case (start == end of previous) is treated as overlapping per the problem spec — verify this with the interviewer. In a trading context, ask: 'Does touching at a boundary count as one continuous session or two?' — showing domain-appropriate clarification.

Common mistakes

Using last[1] = curr[1] instead of Math.max(last[1], curr[1]) — misses the containment case where the current interval is fully inside the last.
Forgetting to sort before the scan — produces incorrect results for unsorted input.
Checking curr[0] < last[1] (strict) instead of <= — misses the touching-at-endpoint case.
Pushing a reference to the intervals[i] array instead of copying — mutations to curr would affect both result and intervals.

Follow-up questions

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

Insert Interval (LC 57) — add one new interval to a sorted non-overlapping list.
Non-overlapping Intervals (LC 435) — minimum removals to eliminate all overlaps.
Meeting Rooms II (LC 253) — minimum number of rooms to schedule all meetings.

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 does sorting by start time work?

After sorting, overlapping intervals are always adjacent. You can never have an interval at index i that overlaps with index i+2 but not i+1, because that would mean i+1 starts between i and i+2 — which would itself overlap with both.

What if two intervals share only a single endpoint (e.g., [1,3] and [3,5])?

By convention (and the problem spec), touching at an endpoint counts as overlapping → merge to [1,5]. The condition curr[0] <= last[1] handles this.

Can you do this without sorting?

Not in general. An O(n log n) lower bound applies because you can sort n numbers in O(n) calls to a merge-intervals oracle. The sort is necessary.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →