Algoritmo di tutti i filmati

Question

Mi sono imbattuto in questo problema che sembra piuttosto interessante. Ci sono alcuni film che vogliamo vedere tutti loro, ma mostrano solo nei seguenti orari:

movieA : 15 
movieB : 14, 15, 17 
movieC : 15, 17 
movieD : 15, 20 

possiamo guardare A a 15, B a 14, C a 17 e D a 20, quindi è possibile guardarli tutti Nota che non puoi guardare C a 15, non fattibile.

Il problema, come avete intuito, è se possiamo guardarli tutti.

Ovviamente possiamo risolverlo con il backtracking, provando tutte le possibilità. C'è un modo migliore per farlo? Ho un'idea di iniziare con i film con il minor numero di volte disponibili prima, in questo modo possiamo trovare la soluzione più veloce se c'è una soluzione, la complessità temporale nel caso peggiore è sempre la stessa.

Esiste un algoritmo migliore per questo problema?

P.S. Come ho chiesto @gen, ho dimenticato di indicare che ogni film è di 1 ora, quindi se ne guardi uno alle 14:00, non ti mancherà quello alle 15:00. Grazie per avermelo chiesto

Answer 1

A seconda dei limiti del numero di film e del numero di possibili orari diversi per ciascun film, è possibile creare un grafico bipartito con i filmati su un lato e le volte nell'altro lato ed eseguire un algoritmo di flusso massimo per determinare la corrispondenza massima. Se è possibile guardare il filmato i all'ora j, aggiungere un bordo tra i nodi corrispondenti nel grafico.

Answer 2

WHILE list of movie times isn't empty 
    1. Sort movie showtime list in order of the number of showtimes. 
    2. Watch next movie according to this sort at the first available time. 
    3. Remove respective time from each movie showtime list and movie 
     from the movie list. 

Python tentativo:

A=[15,'A'] 
B=[14,15,17,'B'] 
C=[15,17,'C'] 
D=[15,20,'D'] 

movies=[A,B,C,D] 


watchOrder = [] 

def f(x): 
    while x: # while x isnt empty 
     x=sorted(x, key=len) 
     watchOrder.append(x[0]) 
     r = x[0][0] 
     x.remove(x[0]) 
     for l in x: 
      if r in l: 
       l.remove(r) 
f(movies) 
print(watchOrder) 

Answer 3

Sembra un problema massima corrispondente su un grafo bipartito. I vertici del grafico sono i due set indipendenti "ore del giorno" e "titoli dei film". I bordi del grafico sono le proiezioni di un particolare film in un momento particolare.

Secondo il Manuale di progettazione dell'algoritmo di Steven Skiena, l'algoritmo più noto è l'algoritmo di Hopcroft-Karp che viene eseguito in O (E * sqrt (V)). E è il numero di spigoli, es. il numero di spettacoli. V è il numero di vertici, es. il numero di film più il numero di ore distinte durante le quali vengono mostrati i film. Negli esempi, E = 8 proiezioni, V = 4 + 4 film distinte volte = 8.

https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

Note formulazione corrispondente è possibile solo perché i film iniziano tutti sull'ora e durano esattamente un'ora. Esse coincidono esattamente o non si sovrappongono affatto.