Arc*_*ect 9 sorting algorithm dynamic-programming greedy
我遇到了这个看起来非常有趣的问题.我们想要观看所有电影,但它们仅在以下时间显示:
movieA : 15
movieB : 14, 15, 17
movieC : 15, 17
movieD : 15, 20
我们可以看到15分,B分14分,C分17分和D分数20分,所以可以全部观看.请注意,你不能在15看C,不可行.
你猜到的问题是我们是否可以全部看到它们.
显然,我们可以通过回溯来解决它,尝试所有可能性.有更好的方法吗？我有一个想法,首先从具有最少可用时间的电影开始,这样我们可以更快地找到解决方案,如果有解决方案,最坏的情况时间复杂性仍然是相同的.
那个问题有更好的算法吗？
PS正如@gen所问,我忘了指出每部电影都是1小时,所以如果你在14:00看一部电影,你就不会错过15点的电影.谢谢你的询问.
根据电影数量的限制和每部电影可能的不同时间的数量,您可以创建一个双面图形,其中一侧是电影,另一侧是时间,并运行最大流量算法来确定最大匹配.如果i可以在时间观看电影j,则在图形中的相应节点之间添加边缘.