algorithm - Disjoint Set Forest 来调度作业

Question

我如何使用不相交的集合森林来安排有惩罚的作业，从而使惩罚最小化？

我们可以先根据惩罚降序排列作业。森林的每个节点 x 将代表作业编号，值 rank[x] 将代表其惩罚。但是我怎样才能最小化这个值 rank[x] 以便最小化惩罚呢？节点的顺序会给我工作的顺序，但是这个算法是什么？我该如何着手制作森林？

Answer 1

您的问题是否来自 CLRS 16-4？最近我也在做这个练习。
通过与 friend 的讨论得到一些提示后，我终于在网上找到了类似的帖子。 CSDN 博客上有两篇帖子是人们分享他们的代码。
阅读他们的帖子后，我认为他们的帖子确实有助于理解使用 Disjoint Set Forest 解决调度作业问题。希望他们也能帮助你。
这两个网站是
http://blog.csdn.net/hechenghai/article/details/6844356 http://blog.csdn.net/jxy859/article/details/6615119