Skip to main content

56. Merge Intervals

mediumAsked at AMD

Given a list of intervals, merge all overlapping ones. AMD uses this to test sorting plus linear scan — the same pattern appears in merging memory-mapped regions, coalescing DMA transfer ranges, and combining address-space reservations in driver memory management.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE and driver-engineering interviews cite Merge Intervals as a recurring medium problem tied to memory range operations.
  • Blind (2025-10)— AMD interview threads list Merge Intervals with a hardware memory coalescing follow-up as a distinctive AMD variant.

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 at 2-3, so they merge into [1,6].

Example 2

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

Explanation: Touching intervals [1,4] and [4,5] merge.

Approaches

1. Sort by start + linear merge

Sort intervals by start time. Scan left to right; if the current interval's start is within the last merged interval's end, extend the merged interval. Otherwise, start a new merged 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 [start, end] = intervals[i];
    if (start <= last[1]) {
      last[1] = Math.max(last[1], end); // extend
    } else {
      result.push([start, end]); // new interval
    }
  }
  return result;
}

Tradeoff: O(n log n) dominated by sort; O(n) for the output. The linear scan after sorting is O(n). This is the optimal approach — you must compare to the last merged interval, not the input's neighbor.

AMD-specific tips

AMD driver and firmware engineers coalesce memory ranges constantly: merging adjacent page mappings, combining DMA scatter-gather entries, or coalescing memory-mapped IO regions. Emphasize that the sort enables a single left-to-right pass. Mention the touching-interval edge case explicitly (start == last[1] should merge) and confirm whether the spec considers touching as overlapping before coding. AMD interviewers credit candidates who ask clarifying questions before coding.

Common mistakes

  • Comparing to the previous input interval instead of the last merged output interval — these are different after merges.
  • Taking min of end instead of max — if a smaller interval is entirely inside the current one, you'd shrink the merged end.
  • Not handling the edge case of a single interval (result initialized with intervals[0] handles this).
  • Forgetting to sort — the algorithm only works on sorted input.

Follow-up questions

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

  • Insert Interval (LC 57) — insert a new interval into a sorted non-overlapping list.
  • Non-Overlapping Intervals (LC 435) — find the minimum number of intervals to remove to make the rest non-overlapping.
  • How would you coalesce a list of virtual memory page ranges in a kernel driver?

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 compare to the last result interval and not the previous input interval?

After merging, the last result interval may have been extended beyond its original end. You need to compare against that extended boundary, not the input's original values.

Do touching intervals (end_i == start_{i+1}) merge?

The problem uses <= in the overlap check (start <= last[1]), so touching intervals do merge — [1,4] and [4,5] become [1,5]. Confirm this interpretation with the interviewer for custom variants.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →