Intervalli massimi non sovrapposti in un albero ad intervalli

Question

Dato un elenco di intervalli di tempo, ho bisogno di trovare il set di intervalli massimi non sovrapposti.

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.

Answer 1

Questo non è un problema NP-Complete. Posso pensare ad un algoritmo O(n * log(n)) usando la programmazione dinamica per risolvere questo problema.

Supponiamo di avere n intervalli. Supponiamo che l'intervallo specificato sia S (nel tuo caso, S = [0000, 2400]). Supponiamo che tutti gli intervalli siano compresi tra S o eliminino tutti gli intervalli non compresi nello S in tempo lineare.

1. Pre-processo:

   • Ordina tutti gli intervalli di loro punti di cominciare. Supponiamo di ottenere un array A[n] di n intervalli.
     • Questo passaggio richiede O(n * log(n)) tempo
   • Per tutti i punti finali di intervalli, trovare l'indice del più piccolo punto che segue dopo è cominciata. Supponiamo di ottenere un array Next[n] di numeri interi n.
     • Se tale punto iniziano non esiste per il punto finale dell'intervallo i, possiamo assegnare n a Next[i].
     • Possiamo farlo nel tempo O(n * log(n)) enumerando n punti finali di tutti gli intervalli e utilizzare una ricerca binaria per trovare la risposta. Forse esiste un approccio lineare per risolvere questo problema, ma non importa, perché il passaggio precedente richiede già il tempo O(n * log(n)).

2. DP:

   • Supponiamo gli intervalli massimi non sovrapposte nella gamma [A[i].begin, S.end] è f[i]. Quindi f[0] è la risposta che vogliamo.
   • Supponiamo inoltre f[n] = 0;
   • equazione transizione Stato:
     • f[i] = max{f[i+1], 1 + f[Next[i]]}
   • È del tutto evidente che la fase DP richiedono tempo lineare.

La soluzione di cui sopra è quello che vengo con al primo sguardo del problema. Dopo di che, penso anche un approccio avido che è più semplice (ma non più veloce nel senso di o-grande):

(con la stessa notazione e le ipotesi come l'approccio DP sopra)

1. Pre-elaborazione: ordina tutti gli intervalli in base ai rispettivi punti fine. Supponiamo di ottenere un array B[n] di n intervalli.

2. Greedy:

   int ans = 0, cursor = S.begin; 
   for(int i = 0; i < n; i++){ 
       if(B[i].begin >= cursor){ 
        ans++; 
        cursor = B[i].end; 
       } 
   } 
   

Quanto sopra due soluzioni escono dalla mia mente, ma il problema è indicato anche come l'attività di problema di selezione, che può essere trovato su Wikipedia http://en.wikipedia.org/wiki/Activity_selection_problem.

Inoltre, Introduzione agli algoritmi discute questo problema in profondità in 16.1.