this is for holding javascript data
Mazdak Farrokhzad edited b) Find the assignment of the rooms.tex
almost 10 years ago
Commit id: d2c416d97392dd371fd1daaeb7af1cc07c19c577
deletions | additions
diff --git a/b) Find the assignment of the rooms.tex b/b) Find the assignment of the rooms.tex
index 524b18c..434445b 100644
--- a/b) Find the assignment of the rooms.tex
+++ b/b) Find the assignment of the rooms.tex
...
return asList(rooms)
\end{verbatim}
\begin{algorithm}[H]
\caption{Finds the rooms that yield the largest number of simultaneously colliding lectures Input: $courses$ is the set of courses to compute for.
\label{alg:efficient-lsp-find}}
\begin{algorithmic}[1]
\Function{findLsp}{$courses$}
\Let{$courses$}{$\Call{sorted}{courses, \{c \to c.start()\}}$}
\Let{$rooms$}{$\Call{priorityQueue}{sorted: \{r \to r.getLast.finish()\}}$}
\For{$i \in courses$}
\Let{$room$}{$[]$}
\If{$len(rooms) > 0 \land \neg collides(i, rooms.peekFirst().getLast())$}
\Let{$room$}{$rooms.removeFirst()$}
\EndIf
\State $room.addLast(i)$
\State $rooms.add(room)$
\EndFor
\Return{$asList(rooms)$}
\EndFunction
\end{algorithmic}
\end{algorithm}
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: