algorithm - 解决问题 : two arrays of starts times and end times, 我可以看多少部电影的策略？

Question

我在面试中被问到这个问题。我知道在 StackOverflow 上，我们不应该要求直接回答 i/w 问题。因此，我会要求正确的方法/提示来解决它，而不是那样

I have been given two array of movie starts times and end times.

int start[], int end[]

对于这两个数组，我必须找到我可以观看的最多电影。在我看来，这与我们必须找到给定间隔的最大重叠的问题完全相反。

我的做法是，如果任何电影没有重叠，我们就应该看。但是，如果有一个重叠，而另一个重叠的持续时间较短，则丢弃这部电影，否则取这部电影。

此算法无法通过此数据集

movie 1:4,8 movie 2 :6,11 movie 3:2,5

该算法正确地消除了 4,8，因为 2,5 更可取。然而，它消除了 6,11 以支持 4,8，尽管我们已经消除了它并且应该考虑它。

我可以知道解决这个问题的正确方法是什么吗？

Answer 1

你可以证明这个问题的贪心选择性质。即，假设您有一个最佳解决方案(电影的最大数量)并考虑第一部电影。如果您未选择的另一部电影的结束时间早于第一部所选电影的结束时间，则您可以将第一部所选电影与结束时间最早且仍然具有有效最优值的电影交换解决方案。因此，您按电影的结束时间对电影进行排序，首先选择结束时间最早的电影，然后迭代选择结束时间最早且与先前选择的电影不重叠的电影。如果您包括排序时间，这将给出 O(n log n) 时间算法，并且排序后的线性时间为 O(n)。