algorithm - 时间部分重叠的加权事件选择

Question

让我们假设我们有 n 个时间表。每个时间表 i 都有一个权重 w(i) ，一个准备时间 prep(i) 和一个休息时间 rest(i) 。

准备时间意味着如果我们选择时间表 i ，我们有义务不选择时间表 i - prep(i) ， i - prep(i) + 1 ... i-1 。

休息时间意味着如果我们选择第 i 个 shedule i ，我们有义务不选择 shedule i+1 , i+2 ... i+rest(i)

我们的任务是根据上述限制选择合适的调度，以最大化W。

注意:对于 i=1 ，我们忽略 prep(i) 。我们假设我们已经准备好了。对于 i=n wh 忽略 rest(i)。

限制:一个时间表的准备时间可以与另一个时间表的休息时间重叠。举个例子，如果我们有 rest(5)=2 ， prep(8)=2 ，我们就可以选择这两个时间表。 rest(5)=2 表示如果我们选择 5 ，则不允许我们选择 6 和 7 。 Prep(8)=2 表示如果我们选择 8 ，则不允许我们选择 6 和 7 。所以我们可以选择 5 和 8。

这个任务最合适的算法是什么？

如果不是因为限制，我们可以说每个时间表都有开始时间 i - prep(i) 和结束时间 i + rest (i) 。我们会有一个加权事件选择问题，所以我们可以用贪心算法得到一个最优的 O(nlogn)。但限制破坏了我的计划。

Answer 1

让f(i)是最佳答案使得 i -th 事件是最后一个。我们可以从事件开始j到事件i如果j < prep(i)和 j + rest(j) < i .换句话说，f(i) = (max of f(j) among all valid j such that j < prep(i) and j + rest(j) < i) + 1 .这个公式导致一个简单的O(N^2)解决方案。

但我们可以做得更好!让我们为最大操作保留一个持久段树(数组中的每个位置一个版本)。最初，它用零填充。对于固定 i , 我们去 prep(i) - 1版本并对 [0, i - 1] 执行最大查询范围。那么f(i)是这个最大值加一的值。之后，我们在i + rest(i)位置更新树(即创建新版本)与 f(i) .就是这样。

我们做 O(N)获取最大值并将一个元素查询更新为持久线段树，因此解决方案需要 O(N log N)时间和空间，看起来不错。然而，它似乎相当复杂。

现在让我们摆脱持久性。我们可以保留一个“正常”(即非持久线段树)并更新位置 i 的值与 f(i)当我们到达 j = i + rest(i) 之后(比方说，通过保留要在每个位置添加的元素向量)。我们不需要再关心第二个限制了。因此，f(i)是 [0, prep(i) - 1] 范围内的最大值加一。找到f(i)后, 我们插入要添加的向量 i + rest(i)位置。

它仍然使用O(N log N)时间，但空间复杂度现在是线性的，我们不再需要持久性线段树(实际上，每次更新只能增加值，我们需要前缀上的最大值，所以我们可以使用二叉索引树代替这里的线段树)。