观看所有电影算法

Question

我遇到了这个问题，看起来很有趣。有几部电影我们想全部观看，但它们只在以下时间放映：

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

我们可以在15点看A，在14点看B，在17点看C，在20点看D，所以可以全部看。注意15级就不能看C了，不可行。

正如您所猜测的，问题是我们是否可以全部观看。

显然我们可以通过回溯来解决，尝试所有的可能性。有更好的方法吗？我有一个想法，首先从可用次数最少的电影开始，这样如果有解决方案，我们可以更快地找到解决方案，最坏情况时间复杂度仍然相同。

有没有更好的算法来解决这个问题？

附注 正如@gen所问，我忘了指出，每部电影都是1小时，所以如果你在14:00看一场，你就不会错过15:00的那一场。谢谢你的询问。

Answer 1

根据电影数量的界限以及每部电影可能的不同时间的数量，您可以创建一个二部图，一侧为电影，另一侧为时间，并运行最大流算法来确定最大匹配。如果电影

i

可以在时间

j

观看，则在图中相应节点之间添加一条边。

Answer 2

看起来像二分图上的最大匹配问题。该图的顶点是两个独立的集合“一天中的时间”和“电影标题”。图表的边缘是特定时间特定电影的放映。

根据 Steven Skiena 的算法设计手册，最著名的算法是 Hopcroft-Karp 算法，其运行时间为 O(E*sqrt(V))。 E是边的数量，即。放映次数。 V是顶点的数量，即。电影数量加上电影放映的不同小时数。在您的示例中，E = 8 次放映，V = 4 部电影 + 4 次不同的时间 = 8。

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

请注意，只有当您的电影都在整点开始并持续一小时时，匹配公式才可能。它们要么完全重合，要么根本不重叠。

Answer 3

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 4

当然，考虑到“观看所有电影算法”，回溯似乎很直观，但效率可能很低。首先优先考虑可用时间最少的电影是一种明智的方法，可能会加快解决方案发现过程。虽然最坏情况的时间复杂度保持不变，但该策略针对现实场景进行了优化。有关高效算法和实际实现的更多见解，请访问网站 zinmanga 应用程序。进一步探索并增强您对算法解决方案的理解。