Greedy Algorithms8 sections · 316 units
Open in Course

Merge Intervals - The Idea

Sort by start

Sort by start time. Then scan left to right. Two intervals [a,b] and [c,d] overlap if c <= b (assuming a <= c after sorting). When they overlap, merge to [a, max(b,d)]. If they do not overlap, start a new merged interval.

It works because after sorting by start, you only need to compare with the last merged interval. Without this insight, you would check each new interval against all previous merged intervals, wasting time.