Selection of dates respecting delay constraints 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 ?
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.