Interval Partitioning
Sort by start. Assign each interval to the first room that is free, else open a new room.
Intervals and Greedy Choices: Assigning rooms
a is 0-3. No rooms yet, so it opens room 1.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(n)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Intervals and Greedy Choices covers these too, in the same run.