Intervals

Back to Index

Use when: merging overlapping ranges, inserting into sorted intervals, detecting conflicts, minimum coverage.

Signal words: merge intervals, insert interval, meeting rooms, non-overlapping, overlapping pairs.

Two Intervals Overlap When

a.start <= b.end AND b.start <= a.end Equivalently: they do NOT overlap when a.end < b.start OR b.end < a.start.

Merge Intervals

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
    if start <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], end)  # extend
    else:
        merged.append([start, end])

Insert Interval

Three phases: add all intervals ending before new one, merge overlapping, add the rest.

Meeting Rooms (can attend all?)

Sort by start, check if any intervals[i].start < intervals[i-1].end.

Minimum Meeting Rooms (how many rooms needed?)

Use a min-heap of end times - greedily reuse the room that frees up earliest.

---

Problems Using This Pattern