algorithm - 找到最小的重叠作业集

Question

一个 friend 给了我一个谜题，他说可以用比 O(n^3) 更好的时间来解决。

给定一组 n 个作业，每个作业都有设定的开始时间和结束时间(重叠很可能)，找到每个作业的最小子集，该子集要么包含该作业，要么包含与该作业重叠的作业。

我很确定最佳解决方案是选择重叠部分未标记最多的作业，将其添加到解决方案集中，然后标记它及其重叠部分。并重复直到所有作业都被标记。
找出哪个作业具有最多未标记的重叠是一个简单的邻接矩阵 (O(n^2))，每次选择作业时都必须重做，以更新标记，使其成为 O(n^3) ).

有没有更好的解决方案？

Answer 1

让 A 成为我们尚未重叠的作业集。

1. 在 A 中找到结束时间 (t) 最小的作业 x。
2. 从开始时间小于t的所有作业中:选择结束时间最大的作业j。
3. 将j添加到输出集中。
4. 从 A 中删除所有与 j 重叠的作业。
5. 重复 1-4 直到 A 为空。

一个简单的实现将在 O(n^2) 中运行。使用interval trees可能在 O(n*logn) 中解决。

为什么它是最佳解决方案背后的基本思想(不是正式证明):我们必须选择一个开始时间小于 t 的工作，以便 x会重叠。如果我们让 S 是开始时间小于 t 的所有作业的集合，可以证明 j 将重叠相同的作业与 S 中的任何工作一样，可能还有更多。由于我们必须在 S 中选择一项工作，因此最佳选择是 j。我们可以使用这个想法通过对工作数量的归纳来形成证明。