Alle Filme ansehen Algorithmus

Question

Ich bin auf dieses Problem gestoßen, das ziemlich interessant scheint. Es gibt ein paar Filme, die wir alle von ihnen sehen wollen, aber sie zeigen nur zu folgenden Zeiten:

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

Wir A bei 15 sehen kann, B 14, C 17 und D 20, so ist es möglich, sie alle zu sehen. Beachte, dass du C nicht mit 15 sehen kannst, nicht lebensfähig.

Das Problem, wie Sie erraten haben, ist, ob wir sie alle beobachten können.

Offensichtlich können wir es mit Backtracking lösen und alle Möglichkeiten ausprobieren. Gibt es einen besseren Weg? Ich habe die Idee, zuerst mit Filmen mit der geringsten Anzahl verfügbarer Zeiten zu beginnen, auf diese Weise können wir die Lösung schneller finden, wenn es eine Lösung gibt, die Komplexität im ungünstigsten Fall ist immer noch dieselbe.

Gibt es einen besseren Algorithmus für dieses Problem da draußen?

P.S. Wie @gen gefragt hat, habe ich vergessen darauf hinzuweisen, dass jeder Film 1 Stunde ist. Wenn du also einen um 14:00 Uhr guckst, wirst du den um 15:00 nicht verpassen. Danke für die Frage.

Answer 1

Abhängig von der Anzahl der Filme und der Anzahl der möglichen Zeiten für die einzelnen Filme können Sie ein zweiteiliges Diagramm mit den Filmen auf der einen Seite und den Zeiten auf der anderen Seite erstellen und einen maximalen Ablaufalgorithmus ausführen die maximale Übereinstimmung. Wenn der Film i zum Zeitpunkt j überwacht werden kann, fügen Sie eine Kante zwischen den entsprechenden Knoten im Diagramm hinzu.

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 Versuch:

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

Sieht aus wie ein maximales Matching Problem auf einem zweiteiligen Graphen. Die Eckpunkte des Graphen sind die zwei unabhängigen Sätze "Stunden des Tages" und "Filmtitel". Die Kanten des Graphen sind Darstellungen eines bestimmten Films zu einer bestimmten Zeit.

Laut Steven Skienas Algorithm Design Manual ist der bekannteste Algorithmus der Hopcroft-Karp-Algorithmus, der in O (E * sqrt (V)) läuft. E ist die Anzahl der Kanten, d. die Anzahl der Vorführungen. V ist die Anzahl der Ecken, d. die Anzahl der Filme plus die Anzahl der Stunden, in denen Filme gezeigt werden. In Ihrem Beispiel E = 8 Gezeigte, V = 4 Filme + 4 verschiedene Zeiten = 8.

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

Beachten Sie die passende Formulierung ist nur möglich, weil Ihre Filme alle auf der Stunde beginnen und genau eine Stunde dauern. Sie stimmen entweder genau überein oder überlappen sich überhaupt nicht.