Merge Intervals

Problem

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return the non-overlapping result covering the same ranges.

Approach

Sort intervals by start time. Iterate and merge: if the current interval overlaps with the last merged one, extend the end; otherwise append a new interval.

When to Use

Overlapping range consolidation — "merge intervals", "insert interval", "meeting room conflicts". Sort by start, sweep and merge. Aviation: airspace reservation merging, calendar/schedule compression.

Complexity

Time	O(n log n)
Space	O(n) (for the output)

Implementation

SolutionTestsChallenge

merge_intervals

Merge Intervals — merge overlapping intervals.

Problem

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return the non-overlapping result covering the same ranges.

Approach

Sort intervals by start time. Iterate and merge: if the current interval overlaps with the last merged one, extend the end; otherwise append a new interval.

When to use

Overlapping range consolidation — "merge intervals", "insert interval", "meeting room conflicts". Sort by start, sweep and merge. Aviation: airspace reservation merging, calendar/schedule compression.

Complexity

Time: O(n log n) Space: O(n) (for the output)

merge_intervals

merge_intervals(
    intervals: Sequence[Sequence[int]],
) -> list[list[int]]

Return merged non-overlapping intervals.

merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]) [[1, 6], [8, 10], [15, 18]]

Source code in src/algo/greedy/merge_intervals.py

def merge_intervals(intervals: Sequence[Sequence[int]]) -> list[list[int]]:
    """Return merged non-overlapping intervals.

    >>> merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]])
    [[1, 6], [8, 10], [15, 18]]
    """
    if not intervals:
        return []

    sorted_iv = sorted(intervals, key=lambda iv: iv[0])
    merged: list[list[int]] = [list(sorted_iv[0])]

    for start, end in sorted_iv[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

tests/greedy/test_merge_intervals.py

"""Tests for merge intervals."""

from algo.greedy.merge_intervals import merge_intervals


class TestMergeIntervals:
    def test_basic(self) -> None:
        result = merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]])
        assert result == [[1, 6], [8, 10], [15, 18]]

    def test_fully_overlapping(self) -> None:
        assert merge_intervals([[1, 4], [2, 3]]) == [[1, 4]]

    def test_no_overlap(self) -> None:
        result = merge_intervals([[1, 2], [3, 4], [5, 6]])
        assert result == [[1, 2], [3, 4], [5, 6]]

    def test_single_interval(self) -> None:
        assert merge_intervals([[1, 5]]) == [[1, 5]]

    def test_empty(self) -> None:
        assert merge_intervals([]) == []

    def test_touching_intervals(self) -> None:
        result = merge_intervals([[1, 2], [2, 3]])
        assert result == [[1, 3]]

Implement it yourself

Run: just challenge greedy merge_intervals

Then implement the functions to make all tests pass. Use just study greedy for watch mode.

Reveal Solution

merge_intervals

Merge Intervals — merge overlapping intervals.

Problem

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return the non-overlapping result covering the same ranges.

Approach

Sort intervals by start time. Iterate and merge: if the current interval overlaps with the last merged one, extend the end; otherwise append a new interval.

When to use

Overlapping range consolidation — "merge intervals", "insert interval", "meeting room conflicts". Sort by start, sweep and merge. Aviation: airspace reservation merging, calendar/schedule compression.

Complexity

Time: O(n log n) Space: O(n) (for the output)

merge_intervals

merge_intervals(
    intervals: Sequence[Sequence[int]],
) -> list[list[int]]

Return merged non-overlapping intervals.

merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]) [[1, 6], [8, 10], [15, 18]]

Source code in src/algo/greedy/merge_intervals.py

def merge_intervals(intervals: Sequence[Sequence[int]]) -> list[list[int]]:
    """Return merged non-overlapping intervals.

    >>> merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]])
    [[1, 6], [8, 10], [15, 18]]
    """
    if not intervals:
        return []

    sorted_iv = sorted(intervals, key=lambda iv: iv[0])
    merged: list[list[int]] = [list(sorted_iv[0])]

    for start, end in sorted_iv[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged