Skip to main content

56. Merge Intervals

mediumAsked at Shopify

Shopify asks Merge Intervals because order-fulfillment, calendar slot bookings, and inventory windows all reduce to it. The interviewer wants to see you sort first, then sweep — and explain why a hash map or graph would be wrong tools here.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Senior Backend Developer + Production Engineer onsite reports list Merge Intervals as a medium-round whiteboard question.
  • Levels.fyi interview reports (2025-11)— Shopify Engineering Lead interview question bank includes Merge Intervals framed as 'merge overlapping fulfillment windows'.

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

Example 2

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

Explanation: Touching intervals are considered overlapping.

Approaches

1. Brute-force all-pairs merge

Repeatedly scan every pair and merge any that overlap until a full pass produces no merges.

Time
O(n^2)
Space
O(n)
function mergeBrute(intervals) {
  const result = intervals.map(i => [...i]);
  let merged = true;
  while (merged) {
    merged = false;
    for (let i = 0; i < result.length; i++) {
      for (let j = i + 1; j < result.length; j++) {
        const [a, b] = result[i];
        const [c, d] = result[j];
        if (a <= d && c <= b) {
          result[i] = [Math.min(a, c), Math.max(b, d)];
          result.splice(j, 1);
          merged = true;
          break;
        }
      }
      if (merged) break;
    }
  }
  return result;
}

Tradeoff: Works but is O(n^2) and ugly to reason about. Useful only as a 'I see it, but I won't ship it' opener so the interviewer hears that you noticed the naive shape before sorting.

2. Sort by start, then sweep (optimal)

Sort intervals by start time. Walk the sorted list; if the current interval overlaps the last merged one (current.start <= last.end), extend last.end; otherwise push current.

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

Tradeoff: Sort dominates at O(n log n); the sweep is O(n). Output space O(n). The textbook answer and what Shopify will accept. The key invariant: after sorting, any interval that overlaps `last` MUST overlap because its start >= last.start; we only need to compare against the most-recent merged interval.

Shopify-specific tips

Shopify's follow-up is usually 'now imagine these are fulfillment slot reservations across timezones — what changes?'. Be ready to discuss epoch-ms normalization, half-open vs closed intervals (Shopify's APIs lean half-open), and what happens when two intervals are added in real time (a TreeMap/red-black tree by start time gives O(log n) inserts; mention it).

Common mistakes

  • Sorting by end instead of start (works for variants like 'min rooms', not for merge).
  • Mutating the input array directly without a `.slice()` — Shopify reviewers will call this out.
  • Treating [1,4],[4,5] as non-overlapping. The convention here is touching = overlapping; clarify with the interviewer first.
  • Comparing only adjacent intervals after sort — that IS correct, but candidates often re-scan the whole result list each iteration, blowing up the time.

Follow-up questions

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

  • Insert Interval (LeetCode 57) — same setup but with a single new interval and a pre-sorted list.
  • Meeting Rooms II — minimum number of rooms needed, returns count not intervals.
  • Online version: intervals arrive one at a time, support add(interval) and currentMerged() in O(log n).
  • What if intervals are 2D rectangles instead of 1D segments?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Can you do this without sorting?

Not in better than O(n log n) worst case. If the value range is small you can bucket-sweep with a difference array in O(n + max), but that's only better when max is small relative to n. Shopify expects the comparison-sort version.

Why compare only against the last merged interval, not all of them?

Because after sorting by start time, all earlier merged intervals end before the current one starts (otherwise they'd already be merged into `last`). The invariant collapses the check from O(k) to O(1) per step.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →