Selezione di date che rispettano i vincoli di ritardo

Question

Ho riscontrato un problema sul lavoro che può essere derivato approssimativamente a questo problema.

Supponiamo che abbiamo una macchina che può essere attivata per fare istantaneamente un'azione. Ci sono diversi (tra 10 a 15) possibili tempi di innesco al giorno.

Devo selezionare esattamente 5 volte al giorno (tra le 00:00 e le 12:00) per rispettare i seguenti vincoli:

• un ritardo minimo tra due selezioni (ad esempio 2 ore)
• un ritardo massimo tra due selezioni (ad esempio 10 ore)

Il ritardo tra l'ultima selezione del giorno e la prima del giorno successivo deve anche essere preso in considerazione per i vincoli.

Ho bisogno di un algoritmo che trovi una soluzione o se non c'è soluzione.

Fino ad ora, non avevo il vincolo sul massimo ritardo. Pertanto, l'ho risolto avidamente, giorno dopo giorno, scegliendo la data più presto possibile fino a quando non vengono selezionate 5 volte. In qualsiasi momento se non era disponibile tempi per il giorno, il problema non aveva una soluzione.

Quindi questo vincolo di ritardo massimo rende il problema NP-completo? O esiste un algoritmo polinomiale che può risolverlo?