56. Merge Intervals

Q: Why does sorting by start guarantee correctness?

After sorting, all intervals starting before the current one have already been processed. If any overlap with the current, they've been merged into the most-recent result interval. So we only need to check the last result entry.

Q: What if intervals were [start, end) instead of [start, end]?

Change <= to <. Half-open intervals don't merge when they touch at the boundary.

mediumAsked at Amazon

Given a list of intervals, merge all overlapping intervals. Amazon asks this to test whether you reach for the sort-then-sweep pattern that's O(n log n).

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

Source citations

Public interview reports confirming this problem appears in Amazon loops.

Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a recurring intervals staple.
Blind (2025-12)— Recurring Amazon interview problem.

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. Sort by start + linear sweep (optimal)

Sort by start. Walk the intervals; if current overlaps with the last in result (current.start <= last.end), extend last.end. Else push.

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

function merge(intervals) {
  if (intervals.length === 0) return [];
  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];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      result.push(intervals[i]);
    }
  }
  return result;
}

Tradeoff: Sort dominates. The sweep is linear because once sorted by start, only the last interval in the result can overlap with the next input.

Amazon-specific tips

Amazon interviewers grade this on the invariant. State out loud: 'After sorting by start, the only interval in the result that could possibly overlap with the next input is the most-recent one. So I compare current.start with last.end and either merge or append.' Without articulating that, the code looks like magic.

Common mistakes

Forgetting Math.max when extending last.end — produces wrong answer when last interval already extends further than the new one.
Using strict < instead of <= for the overlap check — fails on [[1,4],[4,5]] which should merge to [[1,5]].
Sorting by end instead of start — doesn't give the invariant we need.

Follow-up questions

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

Insert Interval (LC 57) — add one new interval, keep result sorted.
Non-overlapping Intervals (LC 435) — count minimum removals.
Meeting Rooms II (LC 253) — count rooms needed.

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 guarantee correctness?

After sorting, all intervals starting before the current one have already been processed. If any overlap with the current, they've been merged into the most-recent result interval. So we only need to check the last result entry.

What if intervals were [start, end) instead of [start, end]?

Change <= to <. Half-open intervals don't merge when they touch at the boundary.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →