Quale algoritmo usare per questo problema?

Question

Sono stato di recente affrontato con un test di interviste Hackerank dove non potevo risolvere correttamente il problema seguente. Non vorrei nominare il problema esatto per scopi della privacy, ma posso dire che non era da nessuna parte in Google con questo nome.

Problema

Vogliamo organizzare un evento con il maggior numero possibile di artisti. Abbiamo ricevuto un elenco di possibili tempi di arrivo performer e durate di performance. La nostra funzione dovrebbe restituire il numero massimo di artisti che possono essere selezionati senza conflitti.

Esempio

n= 5
Arrivi= [1, 3, 3, 5, 7] (Artisti arrivano in questi tempi)

Durazioni= [2, 2, 1, 2, 1] (il tempo necessario per completare le loro prestazioni)
Soluzione= 4

Così al tempo 1 possiamo accettare l'esecutore e finiremo al momento 3. A tempo 3 abbiamo due scelte contrastanti e non importa il quale abbiamo scelto. Il tempo 5 e 7 non sono nemmeno in conflitto.

La mia soluzione

.
1. ha fatto tuple degli arrivi e delle durate su Zipping. Ordinato le tuple prima all'arrivo, quindi sulla durata.
2. Esterno per ciclo per I inizio alla fine. Inizializza il nuovo set in ciascun ITER.
3. Interno per il ciclo per J da I per finire. Controlla se J può essere aggiunto al set senza conflitto. Se il set è più lungo del max salvato.

Source Python

Domande

.
1. Ci sono modi migliori, algoritmi standard per risolvere questo problema?
2. So che ci sono alcuni casi di bordo, per i quali il mio algoritmo non funziona. Hackerank ha valutato il mio algo, e ha superato solo 7/13 casi di test. Cosa potrebbero essere alcuni casi di bordo che mi manca?
3. è un problema di ricerca o un problema di ottimizzazione?

Answer 1

Questo è un semplice Intervallo pianificazione massimizzazione problema, che può essere risolto in < em> o (n log (n)) tempo tramite un semplice algoritmo avido. Il trucco è di ordinare le prestazioni in base alle ora di fine e non ora di inizio .

Ecco la descrizione della soluzione trovata sulla pagina Wikipedia che ho collegato:

---

.

Diversi algoritmi, che possono sembrare promettenti a prima vista, in realtà non trovano la soluzione ottimale:

.

• Selezione degli intervalli che iniziano prima non è una soluzione ottimale, perché se il primo intervallo è molto lungo, accettarlo ci renderebbe rifiutando molte altre richieste più brevi.

• Selezione degli intervalli più brevi o selezione degli intervalli con i meno conflitti non è anche ottimale.

soluzione polinomiale avida

Il seguente algoritmo avido ha Trova la soluzione ottimale:

Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

.

Ogni volta che selezioniamo un intervallo al punto 1, potremmo dover rimuovere molti intervalli al punto 2. Tuttavia, tutti questi intervalli attraversano necessariamente il tempo di finitura di X, e quindi si incrociano tutti. Quindi, al massimo 1 di questi intervalli possono essere nella soluzione ottimale. Quindi, per ogni intervallo nella soluzione ottimale, c'è un intervallo nella soluzione avida. Questo dimostra che l'algoritmo avido cerca in effetti una soluzione ottimale.

Una spiegazione più formale è data da un Argomento di ricarica .

L'algoritmo avido può essere eseguito in tempo o (n log n) , dove n è il numero di attività, utilizzando un punto di pre-elaborazione in cui sono ordinate le attività dai loro tempi di finitura.

---

.

Answer 2

Guarda Intervallo massimo Pianificazione .

Assegna un intervallo $ (s_i, t_i) $ per ogni esecutore, per $ i= 1, \ punti, N $ , il che significa che la prestazione inizia al tempo $ s_i $ e ha una durata di $ t_i - s_i $ .

Assume per ora che tutti gli intervalli sono ordinati per la loro ora di fine. Solo per semplicità assumere anche che tutti i tempi siano distinti (questa ipotesi non è necessaria). Il tuo problema può quindi essere risolto in $ o (n) $ tempo.

Considerare $ (S_1, T_1) $ e Let $ I $ Sii l'insieme di intervalli che intersecarlo (escluso $ (s_1, t_1) $ stessa).

è facile vedere che tutti gli intervalli in $ i $ deve iniziare prima di $ t_1 $ ( altrimenti non si intersecano $ (s_1, t_1) $ ) e termina dopo $ t_1 $ ( Altrimenti $ T_1 $ non sarebbe l'ora di fine minima). Ciò significa che tutti gli intervalli in $ i \ Cup \ {(s_1, t_1) \} $ intersecano tra loro e quindi qualsiasi soluzione può contenere al massimo uno di esse.

Let $ s $ Sii una soluzione (I.e., un sottoinsieme di intervalli di non intersezione a coppie). È sempre possibile convertire $ s $ in una nuova soluzione $ s '$ che contiene $ (s_1, t_1) $ e tale che $ | s '| \ ge | s | $ .

Se $ s \ cap i=vuotyset $ Quindi siamo banalmente fatti da quando possiamo scegliere $ s '= S \ Cup \ {(S_1, T_1) \} $ (Si noti che questo include anche il caso in cui $ (S_1, T_1) \ in s $ ).

Se $ s \ cap I \ neq \ vuoto $ , let $ (s_i, t_i) $ Sii l'intervallo unico in $ s \ cap I $ . Qualsiasi intervallo $ (s_j, t_j) \ in s \ setminus \ {(s_i, t_i) \ {s_i, t_i) \} $ deve soddisfare sia $ s_j> t_i> t_1 $ o $ s_i> t_j> t_1 $ . Quest'ultimo caso è in realtà impossibile poiché contraddicerebbe il fatto che $ (s_i, t_i) \ in s $ . In altre parole, se sostituiamo $ (s_i, t_i) $ con $ (s_1, t_1) $ Otteniamo ancora una soluzione fattibile. Pertanto scegliemo $ s '= s \ cup \ {(s_1, t_1) \} \ setminus \ {s_i, t_i) \} $ .

La linea di fondo è che c'è sempre una soluzione ottimale che contiene $ (s_1, t_1) $ . Pertanto è possibile aggiungere sempre $ (s_1, t_1) $ alla soluzione, elimina tutti gli intervalli in $ s \ cup \ { (S_1, T_1) \} $ e cerca la soluzione ottimale tra gli intervalli rimanenti. Ciò equivale a eseguire l'algoritmo avido che considera gli intervalli in ordine e aggiunge qualsiasi intervallo che si adatta.

Dal tuo istanza sembra che i tempi di partenza siano già ordinati. In questo caso puoi fare il trucco di "invertire il tempo", cioè scambiare i tempi di partenza e di fine, ad esempio modificando $ (s_i, t_i) $ in $ (- T_i, -S_i) $ , che consente di ottenere una classe $ o (n) $ -Time algoritmo saltando il passaggio di smistamento iniziale che già richiederebbe $ \ omega (n \ log n) $ tempo.