56. Merge Intervals

Q: Why does sort by start work but sort by end doesn't?

Sort-by-start gives the invariant that any unmerged interval starts after every prior interval's start, so it can only overlap the most-recent result tail. Sort-by-end loses that invariant — a long earlier interval can still overlap a short later one.

Q: Does this work if some intervals are 'point' intervals like [3,3]?

Yes. The overlap condition curr[0] <= last[1] holds for [last=...3] and [curr=3,3], so they merge. No special handling needed.

mediumAsked at Twilio

Merge Intervals is Twilio's quintessential time-range problem: given an array of intervals, merge all overlapping ones and return the result. Twilio's voice/messaging teams use this pattern for collapsing call-window or rate-limit-window logs, and the interview grades whether you sort first and merge in O(n).

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

Source citations

Public interview reports confirming this problem appears in Twilio loops.

Glassdoor (2026-Q1)— Heavily-reported across Twilio on-site rounds, especially for backend SWE-2 and SWE-3 levels.
LeetCode Discuss (2025-11)— Cited in Twilio messaging-team interview reports as a domain-relevant choice.

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: Intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2

Input

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

Output

[[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Approaches

1. Pairwise compare + iterate to fixed point (rejected)

For every interval, scan the result list and merge if overlapping; repeat until no merges happened.

Time: O(n^2)
Space: O(n)

function mergeBrute(intervals) {
  const result = [];
  for (const iv of intervals) {
    let merged = false;
    for (let i = 0; i < result.length; i++) {
      if (iv[0] <= result[i][1] && result[i][0] <= iv[1]) {
        result[i] = [Math.min(result[i][0], iv[0]), Math.max(result[i][1], iv[1])];
        merged = true;
        break;
      }
    }
    if (!merged) result.push(iv);
  }
  // May need a second pass if a merge created a new overlap
  return result;
}

Tradeoff: Has a subtle correctness bug — a merge can create a new overlap with an already-merged interval, so a single pass isn't enough. Even if you iterate to fixed point, it's O(n^2) in the worst case. Twilio reviewers want to hear 'sort first, then sweep' immediately.

2. Sort by start + linear sweep (optimal)

Sort intervals by start time. Walk through, extending the last merged interval's end when the current overlaps, else appending.

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

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

Tradeoff: Sort dominates at O(n log n). Once sorted, the sweep is O(n) and only ever compares the current to the tail of the result, because any prior merged interval can't overlap a later start by the sort invariant.

Twilio-specific tips

Twilio's voice/messaging teams use this exact pattern in production for collapsing per-recipient delivery windows and rate-limit reservoirs. The interview's bar is the sort-first insight and the 'curr[0] <= last[1]' overlap check including equality (intervals like [1,4] and [4,5] DO merge). Mentioning the domain relevance (window coalescing in messaging) is a strong signal.

Common mistakes

Using strict `<` instead of `<=` in the overlap check — [1,4] and [4,5] should merge.
Sorting by end instead of start — gives wrong answers when intervals nest, e.g., [1,10] and [2,3].
Mutating input intervals when the contract is to return a fresh result — use .slice() on the pushed intervals.

Follow-up questions

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

What if intervals arrived as a stream and you had to maintain merged state in real time? (Use a sorted structure — TreeMap / IntervalTree — for O(log n) per insert.)
What if you needed the COMPLEMENT — the gaps between merged intervals? (One more linear pass over the merged result.)
How would you insert a new interval into an already-merged list? (LC 57 — binary-search the insertion point, then sweep right.)

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 sort by start work but sort by end doesn't?

Sort-by-start gives the invariant that any unmerged interval starts after every prior interval's start, so it can only overlap the most-recent result tail. Sort-by-end loses that invariant — a long earlier interval can still overlap a short later one.

Does this work if some intervals are 'point' intervals like [3,3]?

Yes. The overlap condition curr[0] <= last[1] holds for [last=...3] and [curr=3,3], so they merge. No special handling needed.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →