algorithm - 活动安排

Question

给你一组n个工作。每个工作都与开始时间和结束时间相关联，两者都表示为整数，以及您将从中获得的利润。您必须确定要从事哪些工作才能使利润最大化，请记住，任何时候只能完成一项工作。有没有比O(n ² )效率更好的算法？

Answer 1

您描述的问题称为加权间隔调度，可以在 O(nlogn) 步骤中解决 - 如果作业已经排序，甚至可以在 O(n) 中解决。

快速 Google 搜索将为您提供所需的所有信息。

Answer 2

算法：

给定集合 S = {I1,I2,...,In}：

• 根据开始时间从低到高对S中的区间进行排序。

现在我们已经订购了集合 {J1,J2,...,Jn}。（以 W1,W2,...,Wn 作为利润）

我们将 a(i) 定义为最小索引 k，这样 Jk 的开始时间高于 Ji 的结束时间。如果不存在则返回 -1。

将 D[i] 表示为集合 {Ji,Ji+1,...,Jn} 上的最大利润（如您所述）。

所以我们得到：

D[-1] = 0;
D[i] = maximum{D[i+1],Wi + D[a(i)]}.

• 返回 D[0]。

运行：

对 n 个区间进行排序 - O(nlogn)。

构造 D - O(n)。

总运行时间 = O(nlogn)。