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 ?