Intervals problems, grouped by pattern
Interval problems become simple once the intervals are sorted. From there you merge, intersect, or sweep a line across start and end events to count how many overlap at once.
When to reach for it
- Meetings, bookings or ranges with start and end
- Merge or intersect ranges
- Maximum number of overlapping events
Mistakes to watch for
- Sorting by end when the problem needs start
- Treating touching intervals inconsistently
- Processing end before start at the same timestamp
The 9 problems
1Basics
- Detect overlap unsorted Animated Easy
- Detect overlap sorted intervals Animated Easy
- Interval List Intersections Animated Medium
- Meeting Rooms Animated Easy
- Merge two unsorted intervals Animated Easy
- Merge two sorted intervals Animated Easy
- Merge Intervals Animated Medium
2Line Sweep
- Meeting Rooms II Animated Medium
- Car Pooling Animated Medium