Xem tất cả thuật toán phim

Question

Tôi gặp phải vấn đề này có vẻ khá thú vị. Có một vài bộ phim mà chúng tôi muốn xem tất cả chúng nhưng chúng chỉ hiển thị vào những thời điểm sau:

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

Chúng tôi có thể xem A ở 15, B ở 14, C ở 17 và D ở 20, vì vậy, có thể xem tất cả. Lưu ý rằng bạn không thể xem C ở mức 15, không thể thực hiện được.

Vấn đề như bạn đã đoán, liệu chúng tôi có thể xem tất cả không.

Rõ ràng là chúng tôi có thể giải quyết nó bằng tính năng backtracking, thử tất cả các khả năng. Có cách nào tốt hơn để làm điều đó không? Tôi có ý tưởng bắt đầu với các bộ phim có ít nhất số lần có sẵn trước tiên, theo cách đó chúng tôi có thể tìm giải pháp nhanh hơn nếu có giải pháp, độ phức tạp của trường hợp xấu nhất vẫn như cũ.

Có thuật toán nào tốt hơn cho vấn đề này không?

P.S. Khi @gen hỏi, tôi quên chỉ ra rằng mỗi bộ phim là 1 giờ, vì vậy nếu bạn xem một lúc 14:00, bạn sẽ không bỏ lỡ một lúc 15:00. Cam ơn vi đa hỏi.

Answer 1

Tùy thuộc vào giới hạn về số lượng phim và số lần có thể khác nhau cho mỗi phim, bạn có thể tạo biểu đồ hai chân với các phim ở một bên và thời gian ở phía bên kia và chạy thuật toán dòng tối đa để xác định kết hợp tối đa. Nếu phim i có thể được xem tại thời điểm j, sau đó thêm một cạnh giữa các nút tương ứng trong biểu đồ.

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 nỗ lực:

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

Trông giống như một vấn đề phù hợp tối đa trên một đồ thị hai phía. Các đỉnh của biểu đồ là hai tập hợp độc lập 'giờ trong ngày' và 'tiêu đề phim'. Các cạnh của biểu đồ là các phần trình chiếu của một bộ phim cụ thể tại một thời điểm cụ thể.

Theo Hướng dẫn thiết kế thuật toán của Steven Skiena, thuật toán được biết đến nhiều nhất là thuật toán Hopcroft-Karp chạy trong O (E * sqrt (V)). E là số cạnh, tức là. số lần chiếu. V là số đỉnh, tức là. số lượng phim cộng với số giờ riêng biệt trong thời gian chiếu phim. Trong ví dụ của bạn, E = 8 chiếu, V = 4 bộ phim +4 biệt lần = 8.

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

Lưu ý việc xây dựng phù hợp chỉ có thể vì bộ phim của bạn tất cả bắt đầu vào giờ và kéo dài đúng một tiếng đồng hồ. Chúng trùng khớp chính xác hoặc không trùng lặp.