Skip to main content

56. Merge Intervals

mediumAsked at Canva

Merge all overlapping intervals into the fewest non-overlapping ones — Canva's timeline editor collapses overlapping animation keyframe ranges using exactly this pattern, so expect it early in a phone screen.

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

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 and merge to [1,6].

Example 2

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

Explanation: Intervals that share a boundary point are considered overlapping.

Approaches

1. Brute force (pairwise merge)

Repeatedly scan for any overlapping pair and merge them until no overlaps remain — O(n^2) per pass, multiple passes needed.

Time
O(n^2)
Space
O(n)
function merge(intervals) {
  let merged = [...intervals];
  let changed = true;
  while (changed) {
    changed = false;
    const next = [];
    let i = 0;
    while (i < merged.length) {
      let [s, e] = merged[i];
      let j = i + 1;
      while (j < merged.length && merged[j][0] <= e) {
        e = Math.max(e, merged[j][1]);
        j++;
        changed = true;
      }
      next.push([s, e]);
      i = j;
    }
    merged = next;
  }
  return merged;
}

Tradeoff:

2. Optimal (sort then linear scan)

Sort by start time, then walk the sorted list once — if the current interval's start is within the last merged interval's end, extend it; otherwise push a new interval.

Time
O(n log n)
Space
O(n)
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);
    } else {
      result.push([start, end]);
    }
  }
  return result;
}

Tradeoff:

Canva-specific tips

Canva interviewers ask follow-up: 'What if the input is already sorted?' — know that you can skip the sort and drop the time cost to O(n). Also expect 'What if intervals can be modified in-place?' The boundary condition `start <= last[1]` (not strictly less-than) is the most common off-by-one mistake: intervals that share a single point like [1,4] and [4,5] should merge. Trace through this case explicitly before submitting.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →