I have encountered a problem at work that can be deduced approximately from this problem.
Let's say we have a machine that can be triggered to do an action instantly. There are several possible dates (between 10 and 15) per day.
I have to select exactly 5 dates per day (between 00h00 and 12h00) to respect the following constraints:
- a minimum delay between two selections (for example 2 hours)
- a maximum delay between two selections (for example 10 hours)
The delay between the last selection of the day and the first of the following day must also be taken into account for the constraints.
I need an algorithm that finds a solution or there is no solution.
Until now, I did not have the constraint on the maximum delay. Thus, I solved it greedily, day after day, by choosing the date as close as possible, until 5 dates are selected. At any time if no date was available for the day, the problem had no solution.
Does this maximum time constraint make the NP-complete problem? Or is there a polynomial algorithm that can solve it?