Merge Intervals

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.

Examples

The brute-force approach

For each interval, check every other interval to see if they overlap. If yes, merge them and restart. Repeat until no more merges are possible.

changed = True
while changed:
    changed = False
    for i in range(len(intervals)):
        for j in range(i+1, len(intervals)):
            if overlaps(intervals[i], intervals[j]):
                intervals[i] = merge(intervals[i], intervals[j])
                intervals.pop(j)
                changed = True
                break

O(n²) per pass and potentially many passes. On inputs where all intervals merge into one, this is O(n³) or worse.

Spotting the pattern

This is a Intervals problem. The key question to ask yourself:

After sorting by start time, when does the current interval overlap the last merged interval?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.