Skip to main content

56. Merge Intervals

mediumAsked at Hugging Face

Merge all overlapping intervals into the fewest possible. Hugging Face uses this to test sort-then-sweep reasoning — the same pattern used when merging overlapping token spans from multiple annotators or collapsing overlapping time ranges in a batch inference log.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2026-Q1)— Listed in Hugging Face SWE onsite feedback as a medium sorting + sweep problem.
  • Blind (2025-10)— Hugging Face interview threads cite Merge Intervals as a standard medium problem for data pipeline engineers.

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 — merged to [1,6].

Example 2

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

Explanation: Intervals touching at 4 are considered overlapping.

Approaches

1. Sort by start, then sweep

Sort intervals by start time. Initialize the result with the first interval. For each subsequent interval, if it overlaps with the last merged interval (start <= last.end), extend end to max(last.end, current.end). 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 merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    const [start, end] = intervals[i];
    if (start <= last[1]) {
      last[1] = Math.max(last[1], end);
    } else {
      merged.push([start, end]);
    }
  }
  return merged;
}

Tradeoff: O(n log n) dominated by sort; sweep is O(n). This is the canonical and optimal answer. The key insight: after sorting by start, any overlapping interval must appear consecutively.

Hugging Face-specific tips

State the core insight upfront: 'After sorting by start time, two intervals can only overlap if the second starts at or before the first ends — so a linear sweep is sufficient.' Hugging Face will ask: 'What if the intervals arrive as a stream?' Pivot to an interval tree or sorted insertion structure for dynamic insertion. Connect to ML: 'This merge primitive is exactly how annotation spans from multiple crowd-sourced labelers are reconciled before training a span-extraction model.'

Common mistakes

  • Not sorting first — without sorting, overlapping intervals can be non-adjacent and a single sweep misses merges.
  • Using start < last[1] instead of start <= last[1] — intervals that touch at a single point ([1,4],[4,5]) should also be merged.
  • Not taking max(last.end, current.end) when extending — a nested interval (e.g., [1,10],[2,3]) would incorrectly shrink the end.
  • Mutating the input array's contents — if the original intervals must be preserved, work on a copy.

Follow-up questions

An interviewer at Hugging Face 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) — remove the minimum number to make all intervals non-overlapping.
  • How would you efficiently merge intervals in a system where new intervals arrive continuously?

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 is sorting by start sufficient? What about sorting by end?

Sorting by start guarantees that if two intervals overlap, the one with the smaller start comes first — enabling a single left-to-right sweep. Sorting by end doesn't give this guarantee.

What is the time complexity if the input is already sorted?

O(n) — the sort step is skipped (or O(1) on a sorted array), and only the sweep is needed.

Does the problem handle the case where one interval is entirely contained within another?

Yes — max(last.end, current.end) handles containment: if [2,3] is inside [1,10], last.end stays 10.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →