TechPrep
Searching and orderingReadLabPracticeCheck

Intervals: sort, then sweep

Sort by start (or end) so overlaps become adjacent, then sweep once while comparing only with the last interval kept.

Merge Intervals. Given [start, end] pairs, merge all overlapping intervals and return the result sorted by start.

Signals that point here

The idea

After sorting by start, a new interval can only overlap the last interval in the output. Every earlier output interval ended before the last one began, and the new interval starts no earlier than the last one did.

So the sweep is one comparison: if start <= last_end, extend last_end to the max; otherwise start a new interval. Touching endpoints ([1,4] and [4,5]) count as overlapping here; confirm that with the interviewer.

def merge(intervals: list[list[int]]) -> list[list[int]]:
    merged: list[list[int]] = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Complexity

O(n log n) for the sort, then O(n) for the sweep. O(n) for the output.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: merge([[8, 10], [1, 3], [15, 18], [2, 6], [9, 12]])

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Return the minimum number of meeting rooms needed for a list of meetings.
  2. Insert a new interval into a sorted list of disjoint intervals and merge as needed.
  3. Given two lists of disjoint intervals, return their intersections.

Check yourself

After sorting by start, which interval can a new one overlap?

Only the last one in the merged output.

What bug does max(last_end, end) prevent?

A contained interval shrinking the merged end, e.g. [1,10] then [2,3].

Saved in this browser.