Diciamo che il signor A va al cinema e ottiene un programma di film. Oggi ci sono N film sul programma (1 < N < 50) e per ogni film il momento dell'inizio e l'ora della fine sono dati in minuti. Mr. A vuole vedere quanti minuti di film è possibile. Ma c'è una regola nel cinema: se un film inizia, non puoi guardarlo. In altre parole se il signor A guarda il film 1 e nel frattempo inizia il film 2, il signor A non può guardarlo. Trova il numero massimo di minuti che Mr. A può spendere guardando i film.
All'inizio ho ordinato i film in base alla loro ora di inizio. Quindi ho creato una matrice NxN e l'ho riempita con valori falsi. Ora se Film X e Film Y si intersecano, io gioco nello stesso tempo anche solo per un minuto, quindi Matrix [X] [Y] e Matrix [Y] [X] ottengono il valore vero. Poi controllo il caso quando ogni film è nella soluzione ottimale. Li ho messi in vettoriale. Ora usando la ricorsione, controllo tutte le combinazioni possibili. Se Movie X non ha un'intersezione con tutti i film del vettore, inserisco nel vettore, poiché non ci saranno intersezioni e quindi passerò al film successivo. E così via.
Questo algoritmo funziona, ma penso che sia troppo dispendioso in termini di tempo e, come voglio dire, è "brute-force modificata". C'è un modo migliore per raggiungere la soluzione ottimale.
NOTA: siamo interessati solo al numero massimo di minuti, non al numero massimo di film. Alla fine il programma dovrebbe stampare il numero massimo di minuti, non un elenco dei film che il signor A dovrebbe guardare.