Frontend Beauty
ESC

Type to search the knowledge base.

Merge Intervals

Merge overlapping intervals — sort by start, linear scan, and the calendar/UI variants interviewers stack on top.

intermediate3 min read
  • dsa
  • intervals
  • sorting
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft
  • Uber

The problem

Given an array of intervals where intervals[i] = [startᵢ, endᵢ], merge all overlapping intervals and return an array of the non-overlapping intervals that cover the input.

Input:  [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Input:  [[1,4],[4,5]]
Output: [[1,5]]   // touching ends usually count as overlap — confirm

Input:  [[1,4],[0,4]]
Output: [[0,4]]

Clarify with the interviewer: is [1,4] and [4,5] overlapping? Classic LC says yes (inclusive ends).

Frontend cousins: merge selection ranges in an editor, combine booking slots, coalesce toast time windows, CSS animation segment merge.

Brute force

For each interval, scan all others and merge when they overlap, restarting until stable. Correct-ish, O(n²) or worse, painful bookkeeping. Mention only to discard.

Optimal: sort by start, linear merge

  1. Sort intervals by start ascending.
  2. Seed merged with the first interval (copy).
  3. For each next interval:
    • If start ≤ lastEnd → overlap → lastEnd = max(lastEnd, end)
    • Else push a new interval
function merge(intervals: number[][]): number[][] {
  if (intervals.length === 0) return [];

  intervals.sort((a, b) => a[0] - b[0]);

  const merged: number[][] = [[intervals[0][0], intervals[0][1]]];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    const last = merged[merged.length - 1];

    if (start <= last[1]) {
      last[1] = Math.max(last[1], end);
    } else {
      merged.push([start, end]);
    }
  }

  return merged;
}
Time O(n log n) sort dominates
Space O(n) for output (or O(log n) sort stack depending on engine)

Walk [[1,3],[2,6],[8,10],[15,18]]

next merged
seed [[1,3]]
[2,6] [[1,6]] (2 ≤ 3)
[8,10] [[1,6],[8,10]]
[15,18] [[1,6],[8,10],[15,18]]

Overlap test (commit it)

Two closed intervals [a,b] and [c,d] with a ≤ c overlap iff c ≤ b.
Merged span: [a, max(b,d)].

If ends are half-open [start, end), touching endpoints may not merge — product-dependent.

Edge cases

  • Empty input → []
  • Single interval → itself
  • Fully nested: [1,10] then [2,3] → end stays 10
  • Identical intervals → one
  • Unsorted input — must sort; never assume order
  • Negative times / zero-length [5,5] — still valid intervals

Common bugs

  • Sorting by end instead of start (breaks linear scan invariant)
  • Using < instead of ≤ when inclusive merge is required
  • Mutating input intervals when interviewer forbids it (clone first)
  • Forgetting Math.max on ends when new interval sticks out past the old end
Problem Twist
Insert Interval Merge one new into sorted list
Non-overlapping Intervals Min removals → sort by end
Meeting Rooms Any overlap?
Meeting Rooms II Min rooms → sweep / heap

Interview delivery

  1. Clarify inclusive ends and empty input.
  2. Sort by start → scan.
  3. Code; dry-run nested + disjoint cases.
  4. O(n log n) / O(n).
  5. Name Insert Interval as a follow-up.

Further reading