すべての映画のアルゴリズムを見る

Question

私はかなり面白そうなこの問題を遭遇しました。私たちはそれらのすべてを見たいが、彼らは唯一の次の回で示したいくつかの映画があります。

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

それはですので、私たちは、20で17とDで、14時、15時にCをBを見ることができますそれらをすべて見ることができます。実行可能ではなく15でCを見ることはできません。

あなたが推測したように、私たちはすべてを見ることができるかどうかです。

明らかに、私たちはバックトラックですべての可能性を試して解決することができます。それを行う良い方法はありますか？利用可能な時間が最も少ない映画から始めて、ソリューションがあればもっと速く見つけることができます。最悪の場合の時間の複雑さは同じです。

そこにこの問題のアルゴリズムがありますか？

P.S. @genが尋ねるように、各映画は1時間であることを指摘するのを忘れていたので、14:00に見ると15:00にそれを見逃すことはありません。質問してくれてありがとう。

Answer 1

ムービー数の上限とムービーごとの可能な時間数によっては、一方の側のムービーと他方の側のムービーを持つ2部グラフを作成し、最大フローアルゴリズムを実行して最大一致。時間jで映画iを見ることができる場合は、グラフの対応するノードの間にエッジを追加します。

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の試み：

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

は二部グラフの最大マッチング問題のように見えます。グラフの頂点は「時間帯」と「映画タイトル」の2つの独立したセットです。グラフのエッジは、特定の時間における特定のフィルムの表示である。

Steven Skienaのアルゴリズム設計マニュアルによれば、最もよく知られているアルゴリズムはO（E * sqrt（V））で動作するHopcroft-Karpアルゴリズムです。 Eはエッジの数である。ショーの数Vは頂点の数です。フィルム数とフィルムが表示されている別の時間数を足したものです。あなたのフィルムはすべて時間に開始し、正確に一つの時間続くので、あなたの例では、E = 8回の上映、= 4つの膜+ 4明確倍= 8

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

注マッチング処方Vにのみ可能です。それらは正確に一致するか、まったく重複しません。