Is there an Algorithm for finding the minimum number of classrooms for scheduling n classes in O(nlogn)?

Question

So the question is this :

we have n classes (n intervals) with start time and finish time [si , fi] and we want to find the minimum number of classrooms which we can satisfy all the classes(intervals) without any collusion

the book that I'm reading says we can solve this in O(nlogn) but i cannot find any algorithm better than O(n^2)

it says we should sort them by the starting time but doesn't say the rest of the solution, but that doesn't make any sense because before giving each class a room, shouldn't we check all the other intervals to see if we have a collusion or not? which makes it O(n^2) because for each interval we need to check all the other intervals

am i missing something ?

Answer 1

You can sort the events (an event is either the start of a class or the end of a class) by time. This will take O(n log n).

Now, keep a stack of empty rooms and go through the events in order:

• for each start event take a room from the empty stack and allocate the class to it.
• for each end event put the corresponding room back to the empty stack.

This second phase can be completed in O(n).

By keeping track of the allocations and deallocations done you can easily find the number of needed rooms and the schedule.

If you just need the number of needed rooms this can be simplified to just use a counter instead of the list of rooms. Add one for each start event and subtract 1 for each end event; keep track of the maximum.