FPC22-024.Inspiring Professors

At TU Delft, more and more courses are going back to on-campus lectures. So, naturally, it becomes more difficult to effectively schedule which lecturer can have which lecture hall. They asked you, an algorithm expert, for help on this sub-problem:

There are $n$ lectures that happen at the same time, numbered $1$ to $n$. In the $i$th course, $x_i$ students will attend the lecture on-campus. The lectures are ordered by friendliness of the professor who gives the lecture, with the friendliest lecturer (we all know who that is) giving lecture $1$.

There are $m$ lecture halls. The lecture halls are numbered from $1$ to $m$ and the $j$th lecture hall has capacity $c_j$. The list of $m$ lecture halls is ranked on “niceness”, with the nicest lecture hall on top.

Write a program that reads in the lectures and lecture halls and makes a valid assignment of the halls to lectures. In a valid assignment, the capacity of the hall assigned to a lecture should be greater or equal than the number of students attending.

If there exist multiple valid assignments, compute the assignment which maximizes the niceness of the lecture hall of the friendliest professor. If there are still multiple assignments, maximize the niceness of the lecture hall of lecturer 2, and so on.