IntermediateGreedy & Intervals
Intervals: sort by start, then sweep
Sort intervals by start. Then each one either overlaps the last merged interval (extend it) or starts a new one.
The idea
Unsorted intervals can overlap in any order. Once sorted by start time, an interval can only overlap the most recent merged one, so a single pass decides everything.
Overlap test after sorting: the new start is ≤ the last end.
Worked example
[[1,3], [8,10], [2,6], [15,18]]
- sorted → [1,3], [2,6], [8,10], [15,18]
- [1,3] + [2,6] overlap (2 ≤ 3) → [1,6]
- [8,10] starts after 6 → new; [15,18] → new → [[1,6], [8,10], [15,18]]
In code (Python)
def merge(intervals):
intervals.sort(key=lambda iv: iv[0])
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedO(n log n) for the sort, O(n) for the sweep.
How to spot it
- Meetings, ranges, schedules, “overlapping”, “insert an interval”.
Common mistakes
- Setting the end to the new end instead of the max (a long interval can contain later ones).
- Forgetting to sort.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →