Skip to main content

56. Merge Intervals

mediumAsked at Glean

Glean uses this to assess interval-sweep reasoning — the same logic behind merging overlapping document time-ranges in activity timelines, or collapsing overlapping token spans in entity recognition post-processing.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2026-Q1)— Multiple Glean onsite reports mention Merge Intervals as a medium-difficulty staple in the coding round.
  • Blind (2025-10)— Glean candidates confirm Merge Intervals appears in both phone screens and onsites with follow-ups on meeting rooms and calendars.

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 since 2 <= 3; they merge into [1,6].

Example 2

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

Explanation: Intervals touching at a single point (4,4) are considered overlapping.

Approaches

1. Sort by start + linear scan

Sort intervals by start time. Iterate and extend the last interval in the result if the current interval overlaps. Otherwise, start 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 curr = intervals[i];
    if (curr[0] <= last[1]) {
      // overlapping — extend last interval's end
      last[1] = Math.max(last[1], curr[1]);
    } else {
      result.push(curr);
    }
  }
  return result;
}

Tradeoff: O(n log n) dominated by sorting. After sorting, the linear scan is O(n). This is the canonical and expected answer.

Glean-specific tips

State the key insight before coding: 'If I sort by start time, any overlapping interval must overlap with the most recently added interval in my output — so a single linear scan suffices after sorting.' Glean interviewers will probe the overlap condition: curr[0] <= last[1] (not strictly <), which handles touching-point intervals correctly. Also mention the enterprise use case: calendar event deduplication or timeline compression.

Common mistakes

  • Using curr[0] < last[1] instead of curr[0] <= last[1] — fails for touching intervals like [1,4] and [4,5].
  • Updating last[1] with curr[1] instead of Math.max(last[1], curr[1]) — fails when the current interval is fully contained within the last (e.g., [1,10] then [2,5]).
  • Not sorting before the linear scan — the algorithm only works if intervals are ordered by start time.
  • Mutating the input array — sort operates in-place; if the caller expects the original to be unchanged, copy first.

Follow-up questions

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

  • Insert Interval (LC 57) — given a sorted, non-overlapping list, insert a new interval and merge.
  • Meeting Rooms (LC 252) — can a person attend all meetings? (Detect any overlap after sorting.)
  • Meeting Rooms II (LC 253) — minimum number of rooms required; classic heap problem.

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 do we need to sort first?

Overlapping intervals can only be detected locally (current vs. previous) if the array is ordered by start. Without sorting, a non-overlapping pair might appear between two intervals that should merge.

Is it safe to mutate intervals[i] directly, or should we copy?

The code mutates last[1] in-place for efficiency. If the problem guarantees you can modify the input, this is fine. Otherwise, push a copied array entry: result.push([...curr]).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →