This is a hand-in written by Group 7 (FIRE) for the Algorithms course (TIN092) at Chalmers University of Technology.
Group 7 consists of:
The number of rooms required to schedule a number of lectures is equal to the largest number of lectures which occur at the same time. It is trivial to see that this is the lower bound for the answer; if there are \(k\) lectures which occur at the same time, then there must also be at least \(k\) rooms available in order to be able to schedule them all in separate rooms. Intuitively, if we see time as a line with different levels, and each of the levels represent a room, and then go from left to right trying to place legtures as “far down” as possible, the only reason for placing a lecture at level \(m\) would be if it conflicted with lectures on all the \(m-1\) levels below. Therefore, the upper bound will also be the largest number of lectures colliding at the same time.
We therefore write an algorithm that given a set of lectures, returns the largest number of simultaneously collidi