我被分配了许多任务，每个任务都有一个开始时间和一个结束时间。我应该安排我的一天去做它们。
要求是：
- 任何时候都不能完成一项以上的任务。
- 不能分工
- 最大化总工作时间
我对此的解决方案是：
- 按照与所有其他任务的重叠次数从最少到最多对所有任务进行排名。
- 在上述排名列表中从左到右选择要执行的任务。确保任何要选择的任务与已选择的任务没有重叠。
- 计算时间。
这个对吗？我无法证明。有人有更好的主意吗？
问问题
2771 次
2 回答
4
活动选择问题使用贪心算法最大化任务总数。
但是，您的问题略有不同，因为您希望最大化总时间。
您可以通过解决图中的最短路径问题来解决此问题，其中每个任务都有一个节点。
如果 A 在 B 之前完成，则从任务 A 到任务 B 制作边，并将边上的权重设置为 A 结束和 B 开始之间的时间量。
做一个额外的连接所有任务的起始节点（权重等于任务的开始时间），和一个额外的结束节点连接所有的任务（权重等于任务结束和任务结束之间的时间）那天）。
请注意，每条边上的权重对应于您在使用该边时浪费的不工作时间。
计算此图上的最短路径（例如，使用Dijkstra 算法）将告诉您要以最少浪费时间完成的任务——这与最大化工作时间相同。
例子
在此图中，最短路径是 Start->A->C->End，权重为 3，对应于做作业 A，然后是作业 C，只浪费 3 个小时不工作。
于 2013-11-14T18:59:27.290 回答
1
编辑：我的错误，我的贪心算法解决了最大化完成的工作数量，这与最大工作时间不同。我会在这里留下我的答案，以防人们好奇。
这里有一些关于贪心调度的不错的幻灯片：贪心调度
基本上，与其按重叠次数排名，不如按完成时间的顺序排名。完成时间，我不是指完成需要多长时间，而是何时完成。以这种方式排列的作业，您迭代直到找到开始时间 >= 到当前时间的作业，然后执行该作业。然后你重复，直到你没有时间。
编辑：所以这个算法被标记为贪婪，因为你总是选择具有最早完成时间和有效开始时间的工作作为你的下一个工作。
于 2013-11-14T18:25:32.857 回答