Trova la più piccola serie di lavori sovrapposti

Question

Un amico mi ha dato un puzzle che dice che può essere risolto in meglio di O (n^3).

Dato un insieme di n lavori che hanno ciascuno un orario di inizio e di fine impostato (le sovrapposizioni sono molto possibili), trovare il sottoinsieme più piccolo che per ogni lavoro include quel lavoro o include un lavoro che si sovrappone a quel lavoro.

Sono sicuro che la soluzione ottimale è selezionare il lavoro con la sovrapposizione non contrassegnata, aggiungerlo al set di soluzioni, quindi contrassegnarlo e la sua sovrapposizione. E ripetere fino a quando tutti i lavori sono contrassegnati.
Capire quale lavoro abbia gli overlapper non contrassegnati è una semplice matrice di adiacenza (O (n^2)), e questo deve essere rifatto ogni volta che viene selezionato un lavoro, per aggiornare i segni, rendendolo O (n^3).

C'è una soluzione migliore?

Answer 1

Lascia che sia A l'insieme di lavori che non abbiamo ancora sovrapposto.

1. trovare il lavoro x in A che ha il tempo di fine minima (t).
2. Da tutti i lavori il cui orario di inizio è inferiore a t: selezionare il lavoro j con l'ora di fine massima.
3. Aggiungi j al set di output.
4. Rimuovi tutti i lavori che si sovrappongono a j da A.
5. Ripetere da 1 a 4 fino a A vuoto.

Un'implementazione semplice verrà eseguita in O (n^2). Utilizzando interval trees è probabilmente possibile risolvere in O (n * logn).

L'idea di base perché è una soluzione ottimale (non una prova formale): Dobbiamo prendere un posto di lavoro il cui orario di inizio è inferiore t, in modo che saranno sovrapposte x. Se lasciamo che S sia l'insieme di tutti i lavori il cui orario di inizio è inferiore a t, è possibile mostrare che j si sovrapporrà agli stessi lavori di qualsiasi lavoro in S, oltre eventualmente a più. Dal momento che dobbiamo scegliere un lavoro in S, la scelta migliore è j. Possiamo usare questa idea per formare una prova per induzione sul numero di posti di lavoro.

Answer 2

Possiamo ottenere una soluzione O (nlogn) con un approccio di programmazione dinamico. In particolare, vogliamo considerare la dimensione del set più piccolo, incluso il lavoro k ^th e corrispondenti ai primi lavori k (ordinati per ora di inizio), che indichiamo per S(k). Dovremmo prima aggiungere un lavoro ausiliario (∞, ∞), quindi il risultato sarà la nostra soluzione DP per questo lavoro finale meno uno.

Per calcolare S(k), considerare il lavoro p(k) che termina prima del lavoro k, ma ha l'ora di inizio massima. Notare che p è una funzione crescente. S(k) sarà quindi uno più del minimo S(i) con end(i) > start(p(k)).

Siamo in grado di trovare in modo efficiente questo lavoro mantenendo un cumulo (S(k) ordinato) di potenziali lavori. Dopo aver calcolato ogni S(k), aggiungiamo il lavoro all'heap.Quando vogliamo ottenere un lavoro, rimuoviamo i lavori alla base dell'heap che finiscono troppo presto, finché non ne troviamo uno adatto. Questo richiederà un massimo di O (nlogn), dato che eseguiamo al massimo O (n) di ogni operazione heap (pop/peek/push).

Il resto del compito è calcolare i valori p(k) in modo efficiente. Un modo per farlo è quello di iterare su tutti gli inizio e fine del lavoro (in tempo crescente), tenendo traccia del lavoro di avvio più recente.