寻找最小的重叠工作集

Question

一位朋友给了我一个难题，他说它可以在O(n^3)时间之内得到解决。

给定一组n个任务，每个任务都有开始时间和结束时间（可能会有重叠），找到最小的子集，使得对于每个任务，这个子集要么包含该任务，要么包含与该任务重叠的任务。

我相信最优解是选择具有最多未标记重叠的工作，将其添加到解集中，然后标记它及其重叠。重复这个过程直到所有工作都被标记为止。
找出哪个工作具有最多未标记重叠者是一个简单的邻接矩阵（O(n^2)）问题，但每次选择一个工作后都需要重新进行更新标记，以便更新标记，这使得复杂度达到了O(n^3)。

是否有更好的解决方案？

- kwiqsilver

---

你的解决方案是贪心的，而且并不总是正确的（我可以提供一些它失败的示例），但是它也可以用更好的复杂度进行实现。 - Ivaylo Strandjev

@izomorphius 这是一种贪心算法，出于意图的原因。但我还不能证明它不是最优解。您有什么更好复杂度的解决方案吗？ - kwiqsilver

我知道这很贪心，但是它是不正确的。这里有一个例子：区间：(0, 2) , (1, 4), (3, 6) , (5, 8), (7, 10)。在第一步中，区间 (1,4), (3,6), (5,8) 都覆盖了另外两个区间，所以你可以选择其中任意一个，但是最好的答案是选择 (1,4) 和 (5,8)。还有一些例子，其中覆盖最多区间的区间是唯一确定的，但最佳解决方案仍然不包括它，但这些例子比较难想到。如果你坚持，我可以试着给出一个。 - Ivaylo Strandjev

似乎类似于《算法设计手册》中的“1.2选择正确的工作”，您可以查看谷歌对该书的预览。 - Nick Dandoulakis

我创建了一个图表，其中该算法提供了一个非最优解，因此它被排除在外。但是再仔细思考一下，这看起来像是一个最小支配集，根据维基百科的说法，它是NP-C问题，因此O(n^3)或更好的解决方案是不可能的。 - kwiqsilver

这是最小支配集的一个实例，但我们只处理重叠区间的事实仅限制了问题，以允许多项式时间解决。这类似于2-SAT是3-SAT的特殊情况，并且在P中，而3-SAT是NP完全的。 - interjay

Answer 1

假设我们还没有重叠的工作集合为A。

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

简单的实现需要O(n^2)的时间。使用区间树可能可以在O(n*logn)的时间内解决问题。

为什么这是最优解的基本思想（不是正式证明）：我们必须选择一个开始时间小于t的工作，以便使x被覆盖。如果我们将所有开始时间小于t的工作组成集合S，则可以证明j会与S中的任何工作重叠，可能还会重叠更多。由于我们必须在S中选择一个工作，所以最佳选择是j。我们可以使用这个思想对工作数量进行归纳证明。

- interjay

---

这个算法似乎在区间集 {[0,2], [1,4], [3,10], [5, 6], [7,8]}（来自这个问题）上失败了。它生成的覆盖集是{[1, 4]，[5, 6]，[7, 8]}，而实际上有两个更小的覆盖集：{[0, 2]，[3, 10]}和{[1, 4]，[3, 10]}。 - Ted Hopp

@TedHopp 算法运行正确。它生成了集合 {[1,4]，[3,10]}。请注意，在第2步中，可以选择任何作业，即使它不在A中。 - interjay

Answer 2

我们可以通过动态规划方法实现O(nlogn)的解决方案。特别地，我们要考虑包括第k个作业并匹配前k个作业（按开始时间排序）的最小集合的大小，我们用S(k)表示。我们应该先添加一个辅助作业(∞,∞)，这样结果就是我们对这个最终作业的DP解减去一。

为了计算S(k)，考虑在作业k之前结束但具有最大开始时间的作业p(k)。注意，p是一个递增函数。S(k)将比end(i)>start(p(k))的最小S(i)多一个。

我们可以通过维护一个(S(k)有序min)堆的潜在作业来有效地找到这个作业。在计算每个S(k)后，我们将作业添加到堆中。当我们想要获取一个作业时，我们删除堆底部过早结束的作业，直到找到一个合适的作业。这将总共需要不超过O(nlogn)，因为我们进行的每个堆操作(pop/peek/push)都不超过O(n)。

任务的其余部分是高效计算 p(k) 值。一种方法是迭代所有作业的开始和结束时间（按时间递增），跟踪最新开始的作业。

- Nabb