AlgoScope

Meeting Rooms

Minimum rooms = maximum number of simultaneous meetings. Sweep sorted starts and ends.

Greedy, algorithm, intermediate
Time 2, c starts, 3 open.012345678910abcdefaaabbbccccdddeeeeffft

Intervals and Greedy Choices: How many rooms

Decision, step 4 of 14

t = 2: c starts, taking a room. Open meetings: 3. That is a new maximum, so at least 3 rooms are needed.

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.