1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry I didn't make this clearer: the periods have semantic significance. For example, if there are 8 periods in a day, periods 5-7 represent a specific time-span. I've looked at maximum matching on a bipartite graph, but I've just realized I've phrased my question wrong. Thanks regardless. $\endgroup$ – Li357 Sep 8 at 1:03
  • $\begingroup$ What do you mean by semantic significance? And what does optimal means then? $\endgroup$ – Szymon Stankiewicz Sep 8 at 1:07
  • $\begingroup$ Now that I've thought about the general question, by optimal I meant minimizing some "rest" function, i.e. the total time between all events. That's where the periods come in—being available period 5 is not equivalent to being available period 10, because the difference between two periods determines the "rest" time which I want to minimize. That's my fault and I didn't make that clear. $\endgroup$ – Li357 Sep 8 at 1:14
  • $\begingroup$ So you want to minimize the difference between time of running first and last event? If yes, then you can do the same thing as I described but also iterate over first available time. And of course at the end you need to undo the operation of removing gaps, but the solution still will be minimal since we are keeping the order of periods. $\endgroup$ – Szymon Stankiewicz Sep 8 at 1:17
  • $\begingroup$ Not just the first and last event, basically the sum of time differences between consecutive events (which may be equivalent?). The thing is I want to generalize this so I can maximize the rest function as well to space out events as much as possible along with as little as possible. $\endgroup$ – Li357 Sep 8 at 1:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.