Sort by start (or end) time first — nearly every interval problem begins there. Then sweep left to right, merging or comparing consecutive intervals.
Sub-patterns
- A — Merge Overlapping. Collapse a list of intervals into their disjoint union.
- B — Insert a New Interval. Add one interval into an already-sorted, disjoint list.
- C — Overlap Counting. Count how many intervals overlap at any point.
- D — Interval Intersection. Find the overlap between two lists of intervals.
Practice set (7)
- Medium — Merge Intervals, Insert Interval, Interval List Intersections, Meeting Rooms (Premium), Meeting Rooms II (Premium, also relevant to Heaps and Priority Queues)
- Hard — My Calendar III, Data Stream as Disjoint Intervals
Pending
Merge Overlapping
Collapse a list of intervals into their disjoint union.
Pending
Insert a New Interval
Add one new interval into an already-sorted, disjoint list.
Pending
Overlap Counting
Count how many intervals overlap at any given point.
Pending
Interval Intersection
Find the overlap between two separate lists of intervals.
Notes from readers
Comments — via GitHub