Activity 选择两个资源
Activity selection with two resources
给定 n 个具有开始时间 (Si) 和结束时间 (Fi) 的活动以及 2 个资源。
选择活动以完成最大数量的活动。
我的想法
我尝试用 DP 解决它，但无法用 DP.So 尝试贪婪
解决任何问题
处理方法：先贪心填充resource-1，再贪心填充resource-2（最小结束时间优先）。但这不适用于这种情况 T1(1,4) T2(5,10) T3(6,12) T4(11,15)
贪婪地处理 2:Select 任务并以循环方式分配它。
这也行不通。
谁能帮我解决这个问题？
Activity selection problem可以通过Greedy-Iterative-Activity-Selector算法求解。
基本思路是始终选择下一个 activity，其完成时间在剩余活动中最少，并且开始时间大于或等于先前选择的 activity 的完成时间。我们可以根据活动的完成时间对活动进行排序，以便我们始终将下一个 activity 视为最短完成时间 activity。
更多信息见Wikipedia。
完全不用DP，Greedy解就可以了，虽然比1-resource问题稍微复杂一些
在这里，我们首先按照结束时间对区间进行排序，早的在前。然后，在资源中放入两个"sentinel"区间，结束时间都是-∞。然后，一直抓取最低x.end的区间x，并遵循以下规则：
- 如果x.start在我们两个资源的两个结束时间之前，跳过x不分配它，因为x放不下
- 否则，让 x 覆盖端点为 latest 且仍在 x.start
之前的资源
规则 2 中的贪心策略是这里的关键点：我们想要替换 最新 结束使用的资源，因为这最大化了我们在 "space" other 资源，以适应具有较早开始时间的未来间隔，这使得未来间隔更可能适合。
让我们看问题中的示例，间隔 (1,4)、(5,10)、(6,12) 和 (11,18) 已经排序。我们从具有 (-∞,-∞) 作为 "sentinel" 间隔的两个资源开始。现在取第一个区间 (1,4)，看看它是否合适，所以现在我们有资源 1 有 (1,4) 和资源 2 有 (-∞,-∞)。接下来取(5,10)，这两个资源都能放得下，所以我们选择资源1，因为它最晚结束，现在资源1有(5,10)。接下来，我们取 (6,12)，它只适合资源 2，所以资源 2 有 (6,12)。最后取(11,18)，适合资源1。
因此，我们已经能够使用我们的贪心策略来拟合所有四个区间。
给定 n 个具有开始时间 (Si) 和结束时间 (Fi) 的活动以及 2 个资源。
选择活动以完成最大数量的活动。
我的想法
我尝试用 DP 解决它，但无法用 DP.So 尝试贪婪
解决任何问题处理方法：先贪心填充resource-1，再贪心填充resource-2（最小结束时间优先）。但这不适用于这种情况 T1(1,4) T2(5,10) T3(6,12) T4(11,15)
贪婪地处理 2:Select 任务并以循环方式分配它。 这也行不通。
谁能帮我解决这个问题？
Activity selection problem可以通过Greedy-Iterative-Activity-Selector算法求解。
基本思路是始终选择下一个 activity，其完成时间在剩余活动中最少，并且开始时间大于或等于先前选择的 activity 的完成时间。我们可以根据活动的完成时间对活动进行排序，以便我们始终将下一个 activity 视为最短完成时间 activity。
更多信息见Wikipedia。
完全不用DP，Greedy解就可以了，虽然比1-resource问题稍微复杂一些
在这里，我们首先按照结束时间对区间进行排序，早的在前。然后，在资源中放入两个"sentinel"区间，结束时间都是-∞。然后，一直抓取最低x.end的区间x，并遵循以下规则：
- 如果x.start在我们两个资源的两个结束时间之前，跳过x不分配它，因为x放不下
- 否则，让 x 覆盖端点为 latest 且仍在 x.start 之前的资源
规则 2 中的贪心策略是这里的关键点：我们想要替换 最新 结束使用的资源，因为这最大化了我们在 "space" other 资源，以适应具有较早开始时间的未来间隔，这使得未来间隔更可能适合。
让我们看问题中的示例，间隔 (1,4)、(5,10)、(6,12) 和 (11,18) 已经排序。我们从具有 (-∞,-∞) 作为 "sentinel" 间隔的两个资源开始。现在取第一个区间 (1,4)，看看它是否合适，所以现在我们有资源 1 有 (1,4) 和资源 2 有 (-∞,-∞)。接下来取(5,10)，这两个资源都能放得下，所以我们选择资源1，因为它最晚结束，现在资源1有(5,10)。接下来，我们取 (6,12)，它只适合资源 2，所以资源 2 有 (6,12)。最后取(11,18)，适合资源1。
因此，我们已经能够使用我们的贪心策略来拟合所有四个区间。