Skip to main content

56. Merge Intervals

mediumAsked at Linear

Given a list of intervals, merge all overlapping ones. Linear asks this to test sorting-as-preprocessing and clean interval comparison logic — a practical problem that maps directly to scheduling and event systems, fitting for a project management tool company.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2026-Q1)— Cited as a domain-relevant problem in Linear SWE onsite reports given their scheduling product context.
  • Blind (2025-12)— Mentioned consistently in Linear interview preparation threads as a medium-priority problem.

Problem

Given an array of intervals where intervals[i] = [starti, endi], 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 <= starti <= endi <= 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 [1,4] and [4,5] are considered overlapping.

Approaches

1. Brute force pairwise merging

Repeatedly scan the list for any overlapping pair, merge them, until no merges remain.

Time
O(n^2)
Space
O(n)
// Shown for conceptual clarity only — not recommended in interviews
function merge(intervals) {
  let merged = true;
  while (merged) {
    merged = false;
    for (let i = 0; i < intervals.length; i++) {
      for (let j = i + 1; j < intervals.length; j++) {
        if (intervals[i][0] <= intervals[j][1] && intervals[j][0] <= intervals[i][1]) {
          intervals[i] = [Math.min(intervals[i][0], intervals[j][0]), Math.max(intervals[i][1], intervals[j][1])];
          intervals.splice(j, 1);
          merged = true;
          break;
        }
      }
      if (merged) break;
    }
  }
  return intervals;
}

Tradeoff: O(n^2) and awkward. Use only to establish the intuition, then sort and do a single pass.

2. Sort by start, then single pass merge (optimal)

Sort by start time. Walk through; if the current interval overlaps the last merged interval, extend it. Otherwise push a new one.

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

Tradeoff: O(n log n) dominated by sort; O(1) extra work after sorting. Sorting eliminates the need to check all pairs — after sorting, any overlapping interval must be adjacent.

Linear-specific tips

Linear interviewers connect this to real product scenarios — scheduling, timeline events, roadmap blocks. You can briefly anchor on that: 'This comes up in any system that merges calendar events or timeline spans.' Then name the key insight: sorting by start time means you only ever need to compare the current interval against the last merged one.

Common mistakes

  • Not sorting — without sorting, you'd need to check all pairs (O(n^2)).
  • Using last[1] < intervals[i][0] instead of intervals[i][0] > last[1] — easy to flip the overlap condition.
  • Mutating the original intervals array rather than pushing into a result — the problem expects a new list.

Follow-up questions

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

  • Insert Interval (LC 57) — insert a new interval into a sorted, non-overlapping list.
  • Non-overlapping Intervals (LC 435) — find the minimum number of intervals to remove to eliminate all overlaps.
  • What if intervals can have open vs. closed endpoints?

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 make this O(n log n) instead of O(n)?

Sorting is O(n log n) and is the bottleneck. The merge pass itself is O(n). Together: O(n log n).

How do I detect overlap?

Two intervals [a,b] and [c,d] overlap if and only if c <= b (the start of the second is before the end of the first). After sorting, c >= a is guaranteed.

What if the array has only one interval?

The first interval is pushed to result, and the loop doesn't run. Return [[intervals[0]]] — handled correctly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →