Niclas Alexandersson edited b) Find the assignment of the rooms.tex  almost 10 years ago

Commit id: d9e4bdba9f3adff6436bce7d61e985850bbce4fb

deletions | additions      

       

\section{b) Find the assignment of the rooms}  The earlier algorithm will only give us the number of rooms required required, and not the actual schedules for each room. We therefore write an algorithm that is based on the same principle, but instead of checking how many earlier lectures a given lecture collides with, the algorithm simply tries to find a day room in which the new lecture can be added without conflicting with earlier lectures, and adds a new room if no such room is found.  \begin{verbatim} 

return asList(rooms)  \end{verbatim}  We assume that we have access to some form of sequential data structure with operations $\verb|addLast()|\in \ordo{1}$, and $\verb|getLast()|\in \ordo{1}$ and that our priority queue can be converted to a sequential data structure in linear time.  Complexity:  \begin{subequations}  \begin{align*}