AlgoScope

Interval Partitioning

Sort by start. Assign each interval to the first room that is free, else open a new room.

Greedy, algorithm, intermediate
a goes to room 1.012345678910abcdef111bbbccccdddeeeefff

Intervals and Greedy Choices: Assigning rooms

Decision, step 2 of 8

a is 0-3. No rooms yet, so it opens room 1.

How intervals and greedy choices works

Cost

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

Intervals and Greedy Choices covers these too, in the same run.