Dato un elenco di intervalli di tempo, ho bisogno di trovare il set di intervalli massimi non sovrapposti.Intervalli massimi non sovrapposti in un albero ad intervalli
Ad esempio,
se abbiamo i seguenti intervalli:
[0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130],
[1030, 1400], [1230, 1400]
Inoltre è determinato che il tempo deve essere nell'intervallo [0000, 2400]
.
Il numero massimo di intervalli non sovrapposti è [0600, 0830], [0900, 1130], [1230, 1400]
.
Capisco che il set di impaccamento massimo sia NP-Complete. Voglio confermare se il mio problema (con intervalli che contengono solo l'ora di inizio e di fine) è anche NP-Completo.
E se è così, c'è un modo per trovare una soluzione ottimale in tempo esponenziale, ma con più precoce elaborazione e dati di sfoltimento. O se esiste un algoritmo facilmente rintracciabile per i parametri fissi relativamente facile da implementare. Non voglio andare per un algoritmo di approssimazione.
"massimo" indica il più grande numero_di intervalli o la più lunga _totale durata_ di intervalli? La soluzione di esempio è di 3 intervalli per una durata totale di 6,5 ore. Cosa lo rende massimo, il 3 o il 6.5? –