Merge Intervals

An interval is a start and an end on a number line. Once you sort by start, only the last interval you kept can still overlap the next one.

The most basic skill is telling whether two intervals overlap at all. Find the later of the two starts and the earlier of the two ends. If that start comes at or before that end, they share a point, which in code is max(starts) <= min(ends). The figure shows those two lines on four shapes, and the rhyme to keep is Green before red, overlap ahead. Red before green, gap in between.

The sort is the precondition, since an unsorted pass is wrong rather than merely slow. Settle the endpoint convention before you write anything. Closed intervals [1, 4] and [4, 5] overlap at 4, while half-open [1, 4) and [4, 5) do not, and the only difference in code is <= versus <. To keep the maximum number of disjoint intervals, sort by end so the earliest finisher leaves the most room for the rest. Counting how many intervals cover a point at once belongs to Line Sweep.

Use it when a problem asks whether ranges collide, what they cover once merged, what remains after subtracting one set from another, or how many fit without overlapping.

The problems below start with detecting, merging, and inserting in one sorted list, move through half-open subtraction across two sorted lists, and end with sorting by end to keep the most non-overlapping intervals.