Skip to main content

50. Merge Intervals

mediumAsked at Datadog

Merge all overlapping intervals. Datadog asks this constantly because it's the foundation of compaction — merging overlapping metric chunks, log batches, or active session windows is the same problem.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — direct compaction analog.
  • Blind (2025-12)— Recurring Datadog problem.
  • LeetCode Discuss (2025-11)— Most common Datadog onsite question.

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]]

Example 2

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

Approaches

1. Pairwise merge until stable

Repeatedly find any overlapping pair, merge them, repeat.

Time
O(n^3)
Space
O(n)
// Loop: find any overlapping pair (O(n^2)); merge; remove; repeat until no overlaps. Total O(n^3).

Tradeoff: Cubic. Datadog will reject.

2. Sort by start, sweep merge (optimal)

Sort by start. Maintain a 'current' interval. If next.start <= current.end, extend current.end; else flush and start a new current.

Time
O(n log n)
Space
O(n) output
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const [s, e] of intervals) {
    if (out.length && out[out.length - 1][1] >= s) {
      out[out.length - 1][1] = Math.max(out[out.length - 1][1], e);
    } else {
      out.push([s, e]);
    }
  }
  return out;
}

Tradeoff: Sort cost dominates. Datadog-canonical: this is exactly the inner loop of their TSDB compaction over time-ordered chunks.

Datadog-specific tips

Datadog interviewers will follow up with: 'Now do this on a stream — intervals arrive in sorted order; emit merged ones as they close.' Show that with sorted input, you only need to track the CURRENT open interval; emit when next.start > current.end. Streaming-friendly.

Common mistakes

  • Sorting by end instead of start — doesn't give the right merge order.
  • Using strict > instead of >= for overlap — [1,4] and [4,5] should merge (closed intervals).
  • Updating current.end to next.end without Math.max — would shrink if next.end < current.end.

Follow-up questions

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

  • Insert Interval (LC 57) — insert one into a sorted list.
  • Meeting Rooms II (LC 253) — min concurrent intervals.
  • Datadog-style: streaming compaction over time-ordered chunks.

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?

After sorting by start, any overlapping intervals are adjacent or near-adjacent. A single linear pass merges them all in order.

What about closed vs open intervals?

Convention here is closed: [1,4] and [4,5] overlap. Use >= for overlap check. If the problem uses open intervals, switch to >.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →