Dichiarazione di non responsabilità: il metodo descritto di seguito non è universale, ma spesso può risolvere un problema o aiutarti a trovare la soluzione giusta.
Se c'è una serie di spazi posizionati su un asse (di solito l'asse del tempo o gli indici di un array) e devi sceglierne alcuni in modo ottimale in modo che gli spazi selezionati non si intersechino, allora dovresti provare a utilizzare la programmazione dinamica .
Schema approssimativo della soluzione:
Inizialmente, ordiniamo gli spazi disponibili in base al bordo destro. Iniziamo con le seguenti dinamiche: dp[i] - la risposta per i primi intervalli i.
Ricalcoleremo come segue: in primo luogo, consideriamo la situazione in cui questo intervallo non verrà utilizzato, quindi solo dp[i] = dp[i-1]. Si noti che ciò garantisce che i valori di dp[i] non diminuiscano al crescere di i. E questo è logico, perché. aggiungendo un nuovo divario, non possiamo peggiorare la risposta globale: o semplicemente ignoriamo il nuovo divario o costruiamo una variante più redditizia utilizzandolo. Ora, se vogliamo usare l'intervallo i-esimo, allora possiamo usare quegli spazi i cui bordi a destra sono minori del bordo sinistro dell'intervallo corrente, poiché dobbiamo scegliere un insieme di spazi non sovrapposti. Per fare ciò, inizialmente abbiamo ordinato gli spazi in base al bordo destro, in modo che ora possiamo trovare in modo efficiente la posizione richiesta. Questo può essere fatto analiticamente, se possibile, ma nel caso generale è possibile trovare un gap con un binsearch, il cui bordo destro è minore del bordo sinistro di quello attuale e, allo stesso tempo, il massimo possibile uno. Vogliamo massimizzare il confine giusto per motivi avidi, perché man mano che cresco, la risposta non può che aumentare. Di conseguenza, troviamo la posizione richiesta p e ricalcoliamo da dp[i] a dp[p] e l'i-esimo intervallo.