Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is a list of inclusive intervals like [start, end]. The goal is to combine every set of overlapping intervals and return the smallest list of non-overlapping intervals that covers the same ranges.

The subtle part is that overlap can chain:

  • [1, 3] overlaps [2, 4]
  • [2, 4] overlaps [4, 5]
  • so all three collapse into [1, 5]

That means the problem is not just about checking one pair at a time. It is about recognizing continuous overlap groups.

Why the naive approach gets messy

One brute-force idea is to repeatedly compare every interval with every other interval and merge anything that overlaps.

That approach has two problems:

  • it wastes work because the same ranges get revisited many times
  • it becomes awkward to maintain correctness when a new merge creates another merge opportunity

So the real task is to put the intervals into an order where overlap decisions become local and obvious.

The key insight

Sort the intervals by their starting point first.

After sorting, any interval that can merge with the current interval must appear right next to it or very soon after it. There is no need to scan backward or search the whole list.

Once the intervals are sorted, the algorithm becomes:

  1. Start a result list with the first interval.
  2. Look at the next interval.
  3. If it overlaps the last merged interval, extend the end.
  4. Otherwise, append it as a new disjoint interval.

The overlap test is simple:

  • if next_start <= current_end, the two intervals overlap
  • otherwise, the current merged interval is finished

This also handles the LeetCode detail that touching endpoints count as overlapping, such as [1, 4] and [4, 5].

How to derive the optimal solution

One clean way to derive the final approach is:

  1. Notice that unordered intervals are hard because one merge can affect future comparisons.
  2. Sort by start so potentially related intervals are grouped together.
  3. Keep only one active merged interval at a time.
  4. Extend that active interval while overlaps continue.
  5. Start a new merged interval only when a gap appears.

That produces the standard optimal solution:

  • Time: O(n log n) because sorting dominates
  • Extra space: O(n) for the output list

The scan itself is only O(n), so once the intervals are ordered, the rest is straightforward.

Best way to think about it

Instead of thinking “merge many intervals,” think:

  • sort the intervals
  • maintain the last fully merged block
  • decide whether the next interval extends that block or starts a new one

That framing turns the problem into a simple single-pass sweep.

Python solution

from typing import List


Interval = List[int]


def merge_intervals(intervals: List[Interval]) -> List[Interval]:
    """Merge overlapping inclusive intervals."""
    if not intervals:
        return []

    # Sorting by start time makes every possible merge local.
    sorted_intervals = sorted(intervals, key=lambda interval: interval[0])
    merged_intervals: List[Interval] = [sorted_intervals[0][:]]

    for next_interval in sorted_intervals[1:]:
        _append_or_merge_interval(
            merged_intervals=merged_intervals,
            next_interval=next_interval,
        )

    return merged_intervals


def _append_or_merge_interval(
    merged_intervals: List[Interval],
    next_interval: Interval,
) -> None:
    """Extend the last merged interval or append a new disjoint interval."""
    last_merged_interval = merged_intervals[-1]
    last_merged_end = last_merged_interval[1]
    next_start, next_end = next_interval

    # Touching endpoints still count as overlap for this problem.
    if next_start <= last_merged_end:
        last_merged_interval[1] = max(last_merged_end, next_end)
        return

    merged_intervals.append(next_interval[:])


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        return merge_intervals(intervals)