Skip to main content

56. Merge Intervals

mediumAsked at DRW

DRW frames Merge Intervals as an order-book depth aggregation problem: given a set of bid or ask price-quantity intervals, collapse overlapping ranges into consolidated depth levels. Sorting by start time is mandatory; the merge sweep is O(n).

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2026-Q1)— DRW SWE candidates report interval-merging and scheduling problems as medium-difficulty questions in coding rounds, tied to order-book aggregation context.
  • Blind (2025-10)— DRW interview threads note interval problems are used to test sort-then-sweep pattern, with interviewers asking for the canonical O(n log n) solution.

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

Example 2

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

Explanation: Intervals touching at 4 are considered overlapping.

Approaches

1. Sort by start, then sweep

Sort intervals by start. Walk the sorted list; extend the current merged interval's end if the next interval overlaps, otherwise push the current merged interval and start a new one.

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].slice()];
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const [start, end] = intervals[i];
    if (start <= last[1]) {
      last[1] = Math.max(last[1], end); // extend
    } else {
      result.push([start, end]); // no overlap, start new
    }
  }
  return result;
}

Tradeoff: O(n log n) dominated by sort. The sweep is O(n). This is the only approach needed — there is no way to merge overlapping arbitrary intervals faster than sorting.

DRW-specific tips

DRW interviewers will frame this as: 'You receive 10,000 price-level depth updates per millisecond. Overlapping price ranges represent double-counted liquidity — consolidate them into non-overlapping depth levels.' After solving, they ask: 'What if new intervals arrive in a streaming fashion one at a time?' — you need a balanced BST (e.g., a sorted list with binary-search insertion) to maintain sorted order as you go. Also: 'What is the minimum number of intervals needed to cover [0, n]?' — a greedy interval-covering problem.

Common mistakes

  • Not sorting before the sweep — the merge only works on a sorted sequence.
  • Using start < last[1] instead of start <= last[1] — intervals touching at a single point should be merged.
  • Mutating the input intervals array directly without copying — use last[1] = Math.max(last[1], end) on a copy.
  • Forgetting to push the final merged interval — the loop only pushes when a gap is found, so the last interval must be included.

Follow-up questions

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

  • Insert Interval (LC 57) — insert a new interval into a sorted merged set and re-merge in O(n).
  • How would you merge intervals arriving in a live stream in O(log n) per insertion using a sorted data structure?
  • What is the minimum number of non-overlapping intervals to remove to make the rest non-overlapping (LC 435)?

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 Math.max for the end extension?

A contained interval (e.g., [1,10] followed by [3,5]) would incorrectly shrink the end without Math.max.

What if intervals are already sorted?

Skip the sort — the sweep is O(n). In a trading system, depth updates may arrive pre-sorted by price, making this optimization valid.

How does touching-at-a-point (start == last[1]) work?

The condition start <= last[1] merges touching intervals. This is correct for price-level depth aggregation where a bid at 100 and an ask starting at 100 share a price point.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →