Disjoint Set Forest to schedule jobs

Question

How can I use the disjoint set- forests to schedule jobs with penalties, such that the penalties are minimized?

We could first arrange the jobs in decreasing order on the basis of their penalties. Each node x of the forest will represent the job number and the value rank[x] will represent its penalty. But how can I minimize this value rank[x] so that penalties are minimized? The order of the nodes will give me the order of the jobs, but what will be the algorithm for this? How do I go about making the forest?

Answer 1

Does your problem come from CLRS 16-4 ? Recently I am also doing that exercise.
After gaining some hints from discussion with my friends, I'v finally found similar posts from the Internet. Two posts are on the CSDN blog by people sharing their codes.
After reading their posts, I think their posts really help in understanding the use of Disjoint Set Forest to solve scheduling jobs problem. Hopefully they can help you too.
The two websites are
http://blog.csdn.net/hechenghai/article/details/6844356 http://blog.csdn.net/jxy859/article/details/6615119