用于这个问题的算法？

Question

我最近面对Hackerrank采访测试，在那里我无法正确解决以下问题。我不想为隐私目的命名确切的问题，但我可以告诉它在谷歌上有这个名字。

问题

我们想组织尽可能多的表演者。我们获得了可能的表现者到达时间和性能持续时间的列表。我们的函数应返回无需冲突的最大表现者数。

示例

n= 5
到达= [1,3,3,5,7]（表演者到达这些时间）
持续时间= [2,2,1,2,1]（完成其表演所需的时间）
解决方案= 4

所以在时间1我们可以接受表演者，并将在时间3中完成3.在时间3我们有两个冲突的选择，我们选择了两个冲突的选择。时间5和7也不混淆。

我的解决方案

1. 通过拉链制作了抵达和持续时间的元组。首先在抵达时将元组排序，然后持续时间。
2. 外部循环我从开始完成。初始化每个erter中的新设置。
3. 从i完成j的循环循环。检查是否可以在没有冲突的情况下添加到集合中。如果设置长于Max i保存。

python source

问题

1. 有更好的方式，标准算法来解决这个问题吗？
我知道有一些边缘案例，我的算法不起作用。 Hackerrank评估了我的ALGO，它只通过了7/13的测试用例。什么可能是一些边缘案例，我缺少？
2. 是这是一个搜索问题或优化问题？

Answer 1

这是一个简单的间隔调度最大化问题，可以解决< EM> O（n log（n））通过简单的贪婪算法时间时间。诀窍是根据结束时间而不是开始时间。

以下是在我链接的维基百科页面上找到的解决方案的描述：

---

几种算法，可能看起来很有希望，实际上没有找到最佳解决方案：

• 选择最早开始的间隔不是最佳解决方案，因为如果最早的间隔恰好是很长，接受它会使我们拒绝许多其他更短的请求。

• 选择最短的间隔或选择间隔最少的冲突也不是最佳的。

贪婪多项式解决方案

以下贪婪算法确实找到了最佳解决方案：

Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

.

每当我们在步骤1中选择间隔时，我们可能必须在步骤2中删除多个间隔。然而，所有这些间隔都必须通过X的整理时间，因此它们都互相交叉。因此，最多可以在这些间隔中获得最佳解决方案。因此，对于最佳解决方案中的每个间隔，贪婪解决方案中存在间隔。这证明了贪婪算法确实找到了最佳解决方案。

更正式的解释是由a 充电参数。

可以在时间 o（n log n），其中 n 是任务的数量，使用该任务的预处理步骤通过他们的整理时间。

---

Answer 2

查看最大间隔调度。

分配一个间隔 $（s_i，t_i）$ 到每个执行者，对于 $ i= 1，\ dots， n $ ，意味着性能在时间 $ s_i $ ，并且具有 $ t_i - s_i的持续时间$ 。

现在假设所有间隔都按其结束时间排序。 仅仅为简单起见，也可以所有时间都不同（这种假设是不必要的）。 然后，您的问题可以在 $ o（n）$ 时间中解决。

考虑 $（s_1，t_1）$ ，让 $ i $ 是一组间隔相交（不包括 $（s_1，t_1）$ 本身）。

很容易看到 $ i $ 必须在 $ t_1 $ （否则它们不会间隙 $（s_1，t_1）$ ）和 $ t_1 $ （否则 $ t_1 $ 不会是最小结束时间）。这意味着 $ i \ cup \ {（s_1，t_1）\} $ 相交，因此任何解决方案都可以包含在其中最多的一个解决方案中。

让 $ s $ 是一个解决方案（即，成对非交叉间隔的子集）。 将 $ s $ 转换为新的解决方案 $ s'$ s'$ s'$ ，其中包含 $（S_1，T_1）$ ，使 $ | s'| \ ge | s | $ 。

如果 $ s \ cap i=imptyset $ 然后我们才能完成，因为我们可以选择 $ s'= s \ cup \ {（s_1，t_1）\} $ （请注意，这也包括其中 $（s_1，t_1）\中的情况下的情况>）。

如果 $ s \ cap i \ neq \ imptyset $ ，Let $（s_i，t_i）$ 是 $ s \ cap i $ 中的唯一间隔。任何间隔 $（s_j，t_j）\在s \ setminus \ {（s_i，t_i）\} $ 必须满足 $ s_j> t_i> t_1 $ 或 $ s_i> t_j> t_1 $ 。后一种情况实际上是不可能的，因为它将与S $ 中的 $（s_i，t_i）\中的事实相矛盾。 换句话说，如果替换 $（s_i，t_i）$ 使用 $（s_1，t_1）$ 我们仍然获得可行的解决方案。因此，我们选择 $ s'= s \ cup \ {（s_1，t_1）\} \ setMinus \ {（s_i，t_i）\} $ 。

底线是，始终存在包含 $（s_1，t_1）$ 的最佳解决方案。因此，您可以始终添加 $（s_1，t_1）$ 到您的解决方案，删除 $ s \ cup \ { （S_1，T_1）\} $ ，并在剩余间隔中查找最佳解决方案。 这增加了运行贪婪算法，该算法以顺序计算间隔，并添加任何适合的间隔。

从您的实例中似乎已经对起始时间进行了分类。在这种情况下，您可以执行“反转时间”的技巧，即，交换起始和结束时间，例如通过更改 $（s_i，t_i）$ 进入 $（ - t_i，-s_i）$ ，它允许您获取 $ o（n）$ -time算法通过跳过已经要求 $ \ oomega（n \ log n）$ 时间的初始排序步骤。