Merge Intervals

When intervals are sorted by their start points, all candidates that could possibly overlap with an active interval appear consecutively. One linear sweep comparing each candidate's start with the current running interval's finish suffices to either stretch the boundary or lock the interval and begin a fresh one.

Full solution

Sort by start and sweep once, stretching the running interval's end with max() whenever the next start falls at or before it. The graph/connected-components approach is O(n^2) and never worth writing here.

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda iv: iv[0])
    result: list[list[int]] = []
    for start, end in intervals:
        if result and start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [];
  for (const [start, end] of intervals) {
    const last = result[result.length - 1];
    if (last && start <= last[1]) {
      last[1] = Math.max(last[1], end);
    } else {
      result.push([start, end]);
    }
  }
  return result;
}

The theory behind it

Intervals — the ground this problem stands on. All Intervals problems

What Intervals is

An interval is a continuous range of numbers defined by two values: a start point and an end point. Think of a calendar event booked from two to four o'clock, or a cut segment on a ruler. Because each interval covers every number between its boundaries, two intervals can sit apart with empty room between them, touch at an edge, or overlap across a shared span of numbers.

When to reach for it

Reach for intervals when the input consists of start and end pairs representing time slots, schedules, ranges, or geometric segments. Phrasings asking to merge overlapping blocks, insert a new meeting into a busy calendar, find the minimum number of conference rooms needed, or count how many intervals must be removed to eliminate overlaps all point directly to interval patterns. Whenever problems involve resource contention over time, think intervals.

How the pattern works

The opening move is almost always sorting the intervals by their start times, or occasionally by their end times. Once ordered, compare the current interval with the previous one. If the new start time is less than or equal to the previous end time, the two intervals collide; merge them by stretching the previous end time to the maximum of both ends. If they do not collide, the previous interval is finished, so append it to the result and start tracking the new one. For room counts, split intervals into separate start and end events.