1
$\begingroup$

I encountered an issue at work that can be derived approximatively to this problem.

Let say we have a machine that can be triggered to instantly do an action. There are several (between 10 to 15) possible triggering times per day.

I have to select exactly 5 times per day (between 00:00 a.m. and 12:00 p.m) to respect the following constraints:

  • a minimum delay between two selections (for instance 2 hours)
  • a maximum delay between two selections (for instance 10 hours)

The delay between the last selection of the day and the first of the next day also has to be considered for constraints.

I need an algorithm that find one solution or if there is no solution.

Until now, I did not have the constraint on the maximum delay. Thus, I solved it greedily, day after day, picking the soonest possible date until 5 times are selected. At any moment if no times was available for the day, the problem had no solution.

So does this maximum delay constraint make the problem NP-complete ? Or is there a polynomial algorithm that can solve it ?

$\endgroup$
1
$\begingroup$

This can be solved in polynomial time using dynamic programming.

We'll build up an array $A$. The meaning of the array is as follows: if $t$ is a time on day $d$ and $i \in \{1,2,3,4,5\}$, then $A[t,i]=1$ means that it's possible to build a schedule for days $1..d$ that ends at time $t$ and obeys all the constraints (minimum delay $\ge$ 2 hours, maximum delay $\le$ 10 hours, exactly 5 times chosen on days $1..d-1$ and exactly $i$ times chosen on day $d$).

Note that, once you've filled in $A[1..t-1,1..5]$, you can fill in $A[t,1..5]$ via a simple recurrence relationship: e.g.,

$$A[t,1] = \lor_{t'} A[t',5]$$

where $t'$ ranges over all times that are on the day before $t$, and that fall at least 2 hours before and at most 10 hours before $t$; and

$$A[t,i] = \lor_{t''} A[t'',i-1] \text{ for } i=2,3,4,5$$

where $t''$ ranges over all times that are on the same day as $t$ but before $t$, and that fall at least 2 hours before and at most 10 hours before $t$.

Thus, you can fill in the array $A$ entry-by-entry, in order of increasing $t$. This will give a linear-time algorithm for finding a valid schedule that meets your constraints.

$\endgroup$
  • $\begingroup$ I understand the overall technique. But can you give more details on how the minimum & maximum delay constraints are considered when executing the recurrence ? Thank you. $\endgroup$ – Vince Feb 27 at 16:14
  • $\begingroup$ @Vince, Doh! I forgot to write that part. Sorry! Thanks for pointing that out. I edited my question to add the part that ensures those constraints are met. $\endgroup$ – D.W. Feb 27 at 16:21
  • $\begingroup$ Ok I also understand better the meaning of A now. So it indeed efficiently find wheter a solution exists. How to properly extract one solution after that ? $\endgroup$ – Vince Feb 27 at 16:30
  • $\begingroup$ By starting by end, that is to say A[365, 5], any valid time may be selected. Then constraints should be applied again to leave any A[365, 4] that does not fit with the chosen time for A[365, 5], and so on... Do you think this work ? $\endgroup$ – Vince Feb 27 at 16:44
  • $\begingroup$ @Vince, I don't know; I guess you'd have to flesh out the approach (I think I get a partial sense of what you have in mind, but it sounds still rather vague at this point) and then see if you can prove it correct. $\endgroup$ – D.W. Feb 27 at 17:09

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.