this is for holding javascript data
Niclas Alexandersson edited a) As few classrooms as possible.tex
almost 10 years ago
Commit id: 8d5c258fbcdc8771c1606e7fd767643372655192
deletions | additions
diff --git a/a) As few classrooms as possible.tex b/a) As few classrooms as possible.tex
index 52bc08d..5e2cad7 100644
--- a/a) As few classrooms as possible.tex
+++ b/a) As few classrooms as possible.tex
...
\section{a) As few classrooms as possible}
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 colliding lectures. The algorithm goes through all lectures in start time order, and compares them against the set of lectures which the previous lecture collided with, to see if they also collide with these. The algorithm then returns the
largest size of the
collision set. largest set of colliding lectures encountered.
\begin{verbatim}