Zobacz wszystkie algorytmy filmów

Question

Natknąłem się na ten problem, który wydaje się całkiem interesujący. Istnieje kilka filmów, które chcemy oglądać wszystkie z nich, ale pokazują one tylko w następujących godzinach:

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

Możemy oglądać w 15, B w 14 C na 17 i D na 20, więc jest to można oglądać je wszystkie. Pamiętaj, że nie możesz oglądać C w wieku 15 lat, nie można tego zrobić.

Jak można się domyślić, problem polega na tym, czy możemy obejrzeć je wszystkie.

Oczywiście możemy to rozwiązać poprzez cofnięcie, wypróbowanie wszystkich możliwości. Czy istnieje lepszy sposób na zrobienie tego? Mam pomysł na rozpoczęcie od filmów z najmniejszą liczbą dostępnych czasów, dzięki czemu możemy szybciej znaleźć rozwiązanie, jeśli istnieje rozwiązanie, w najgorszym przypadku złożoność czasu jest wciąż taka sama.

Czy istnieje lepszy algorytm dla tego problemu?

P.S. Jak prosił @gen, zapomniałem zaznaczyć, że każdy film ma 1 godzinę, więc jeśli obejrzysz go o 14:00, nie przegapisz tego o 15:00. Dzięki, że pytasz.

Answer 1

W zależności od granic liczby filmów i liczby możliwych różnych czasów dla każdego filmu, można utworzyć dwustronny wykres z filmami po jednej stronie i czasami po drugiej stronie i uruchomić algorytm maksymalnego przepływu w celu określenia maksymalne dopasowanie. Jeśli film i może być oglądany w czasie j, dodaj krawędź między odpowiednimi węzłami na wykresie.

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 próba:

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

Wygląda maksymalnej problemu z dopasowaniem na dwustronnym wykresie. Wierzchołki wykresu to dwa niezależne zestawy "godziny dnia" i "tytuły filmów". Krawędzie wykresu to pokazy konkretnego filmu w określonym czasie.

Zgodnie z algorytmem projektowania algorytmem Steven Skiena, najbardziej znanym algorytmem jest algorytm Hopcroft-Karp, który działa w trybie O (E * sqrt (V)). E to liczba krawędzi, tj. liczba pokazów. V to liczba wierzchołków, tj. liczba filmów plus liczba różnych godzin, podczas których wyświetlane są filmy. W przykładzie, E = 8 pokazy, V = 4 + 4 odrębne filmy razy = 8.

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

Note preparat dopasowanie jest możliwe tylko dlatego, że Twoje filmy wszyscy zaczynają na godzinę i trwać dokładnie jedną godzinę. Są albo dokładnie zbieżne, albo w ogóle się nie pokrywają.