Merge Intervals

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    out = []
    for start, end in intervals:
        if not out or start > out[-1][1]:
            out.append([start, end])           # new interval
        else:
            out[-1][1] = max(out[-1][1], end)  # stretch
    return out

Merge Intervals. You get a list of intervals, each with a start and an end. Merge every pair that overlaps, and return what's left, with no overlaps.

Here are six: eight to ten, one to three, fifteen to eighteen, three to five, nine to twelve, and two to six. The answer is three intervals: one to six, eight to twelve, and fifteen to eighteen.

The slow way compares every pair. That's n squared checks. And every merge makes a longer interval that needs checking again, so you scan over and over.

Instead, sort by start. Now anything that overlaps an interval comes right after it. Sweep left to right with one open interval. If the next start is at or before its end, stretch the end. If not, close it and open a new one.

In code: sort, then loop over the intervals. If the output is empty, or the start is past the last end, append a new interval. Otherwise, set the last end to the max of the two ends.

Let's sweep. One to three opens. Two starts before three, so the end stretches to six. Three to five sits inside, and the max keeps six. Eight is past six: close one to six, and open eight to ten. Nine overlaps, so stretch to twelve. Fifteen is past twelve: close it, and open fifteen to eighteen. Three intervals.

Sorting takes n log n time, and the sweep is one pass. The output needs up to n space.

Sort by start, then sweep and stretch. That's Merge Intervals.