How to schedule events optimally given when the events are available?

Question

Suppose I had a dictionary that contains events and the corresponding periods they are occurring. For example:

$$ \begin{align} \textrm{Event 1} &\rightarrow \textrm{[1, 2, 3]} \\ \textrm{Event 2} &\rightarrow \textrm{[2, 4]} \\ \textrm{Event 3} &\rightarrow \textrm{[4]} \\ \textrm{Event 4} &\rightarrow \textrm{[2, 3]} \end{align} $$

How would I go about generating a schedule so that the events are scheduled optimally? For the example above, one possible optimal schedule would be:

$$ \begin{align} \textrm{Period 1} &\rightarrow \textrm{Event 1} \\ \textrm{Period 2} &\rightarrow \textrm{Event 2} \\ \textrm{Period 3} &\rightarrow \textrm{Event 4} \\ \textrm{Period 4} &\rightarrow \textrm{Event 3} \\ \end{align} $$

Is there any way to do this in better than checking every permutation? This seems like the reverse of the graph-coloring problem for scheduling, so is there any way to construct a graph to encapsulate this relationship and maybe find a shortest path? Can someone point me in the right direction on how to approach this?

Answer 1

I assume that by "optimally" you mean using the least number of periods. Thirst thing is that you can renumerate the dictionary such that there are no gaps in available periods, so:

$$ \text{Event 1} \rightarrow\ [1, 2, 10]\\ \text{Event 2} \rightarrow\ [3, 5, 11, 12]\\ $$

becomes

$$ \text{Event 1} \rightarrow\ [1, 2, 5]\\ \text{Event 2} \rightarrow\ [3, 4, 6, 7]\\ $$

So now the largest number on the right side is not greater then the sum of sizes of lists on the right side. Assume that, there are $n$ events and sum of sizes of lists on the right side is $m$. Now to check if there is a solution, which uses only first $i$ periods we can reduce the lists to the numbers smaller or equal to $i$, so for $i=4$ this example will change to: $$ \text{Event 1} \rightarrow\ [1, 2]\\ \text{Event 2} \rightarrow\ [3, 4]\\ $$ Now to check if there is a solution for given $i$ we can create bipartite graph with events on one side, periods on the other side and edges between event $e$ and period $p$ if $e$ is available during $p$. If there is matching of size equal to $n$ in this graph then we can schedule events using only first $i$ periods. If we find smallest $i$ with such property then we have a solution to our original problem. It's easy to see that if there is such matching for $i$ then there is also for $i+1$, so we can use binary search to find smallest $i$. This solution will work in time $O(m\sqrt{n+m}\log{m})$ where $O(m\sqrt{n+m})$ comes from finding matching and $O(\log{m})$ comes from binary search.