Sottoinsiemi mutuamente sovrapposti di attività - algoritmo, avido

Sto preparando per una finale e questo era un problema pratico. Non è un problema di compiti a casa.

Come faccio ad attaccare questo? Inoltre, più in generale, come faccio a sapere quando utilizzare la programmazione Greedy vs. Dynamic? Intuitivamente, penso che questo sia un buon posto per usare avidi. Sto anche pensando che se potessi in qualche modo creare una linea ortogonale e "spazzarla", controllando il numero di incroci in ogni punto e aggiornando un massimo globale, allora potrei semplicemente restituire il massimo alla fine della scansione. Non sono sicuro di come piangere sweep algoritmicamente però.

un. Ci viene dato un insieme di attività I1 ... In: ogni attività Ii è rappresentata dal suo punto di sinistra Li e dal suo punto di destra Ri. Progettare un algoritmo molto efficiente che trovi il numero massimo di sottoinsiemi di attività reciprocamente sovrapposte (scrivi la tua soluzione in inglese, bullet by bullet).

b. Analizza la complessità temporale del tuo algoritmo.

La soluzione proposta:

Ex set: {(0,2) (3,7) (4,6) (7,8) (1,5)} Max è 3 nell'intervallo 4-5

1) Dividere i punti iniziale e finale in due array separati e ordinarli in ordine decrescente

Punti iniziali: [0,1,3,4,7] (SP) Punti finali: [2,5,6,7,8] (EP)

So che posso usare due indicatori per simulare lo sweep del piano, ma non sono esattamente sicuro di come.

risposte:

Direi che la tua idea di sweep è buona.

Non devi preoccuparti dello spazzamento planare,basta usare i punti di inizio / fine. Metti gli elementi in coda. In ogni passo prendi l'elemento più piccolo dal fronte della coda. Se si tratta di un punto iniziale, incrementare il numero di attività correnti, altrimenti diminuirlo.

Dal momento che non è necessario indicare quali attività si sovrappongono - solo il conteggio di esse - non è necessario preoccuparsi della durata dei compiti specifici.

Per quanto riguarda la tua domanda avida vs DP, nella mial'opinione non professionale avida potrebbe non fornire sempre una risposta valida, mentre DP funziona solo per problemi che possono essere suddivisi in sottoproblemi più piccoli. In questo caso, anche io non chiamerei la tua soluzione di spazzamento.