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 21 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
- Insert Interval Medium
- Non-overlapping Intervals Medium
- My Calendar I Medium
- Count Days Without Meetings Medium
- Minimum Number of Arrows to Burst Balloons Medium
- Two Best Non-Overlapping Events Medium
- Partition Labels Medium
2Line Sweep
- Meeting Rooms II Animated Medium
- Car Pooling Animated Medium
- Employee Free Time Hard
- Divide Intervals Into Minimum Number of Groups Medium
- Rectangle Area II Hard
- Minimum Platforms Medium