Merge Intervals

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given a list of intervals, merge every group of overlapping intervals and return the result. Each interval is a pair [start, end] with start ≤ end. Two intervals overlap if they share at least one point, so [1, 3] and [3, 5] merge into [1, 5]. The input is not sorted.

    You'll meet this problem directly, and even more often in disguise: merging calendar busy times, combining IP address ranges, or collapsing log time windows. Original problem: LeetCode 56.

    Example

    [1, 3] and [2, 6] overlap, so do [8, 10] and [9, 12]; [15, 18] stays on its own.
    [1, 3] and [2, 6] overlap, so do [8, 10] and [9, 12]; [15, 18] stays on its own.
    Input:  [[8,10], [1,3], [15,18], [2,6], [9,12]]
    Output: [[1,6], [8,12], [15,18]]
    Input:  [[1,4], [4,5]]
    Output: [[1,5]]          # touching endpoints count as overlap

    Constraints (assumed)

    • 1 ≤ n ≤ 100,000 intervals.
    • 0 ≤ start ≤ end ≤ 10⁹.

    What this question tests

    • Seeing that sorting turns a messy all-pairs problem into a simple left-to-right scan.
    • Getting the overlap condition and the merged end exactly right, including the containment case.
    • Clean code and a clear complexity argument.

    Questions to ask first

    1. Do touching intervals merge? Is [1, 3] with [3, 5] one interval or two? (Here: they merge.)
    2. Is the input sorted? (Here: no.)
    3. Can I modify the input, or must I return a new list?
    4. Are intervals closed [a, b] or half-open [a, b)? This changes the overlap test from ≤ to <.