Intervals
Sort by start or end, then sweep. Covers merging, meeting rooms and scheduling.
Newinterview weight 6011 problems0 visualisers
18
mastery
Attempts logged
0
Predicted success on the next one
33%
Solved here
0 / 11
What you actually need to hold in your head
- Two intervals overlap when each starts before the other ends
- Sort by end for maximum non-overlapping count
- Sweep line with plus one and minus one events
- A min heap of end times counts rooms
Patterns in this topic
The trigger phrases are what you are training yourself to notice.
Merge IntervalsO(n log n)
Sort by start. Extend the last interval while the next one starts before it ends, otherwise push a new one.
overlapping rangesmerge or insert an interval
Sweep Line / Event CountingO(n log n)
Turn each interval into a start event of plus one and an end event of minus one, sort the events and track the running total.
max concurrent meetingscar pooling capacity
Intervals problems
Ordered by sheet phase, so the early ones are the highest signal.
0 / 11 solved