首页 > 试题广场 >

（调度问题变形）对于带截止时间和惩罚的单位时间任务调度问题，

[问答题]

（调度问题变形）对于带截止时间和惩罚的单位时间任务调度问题，考虑如下算法。初始时令n个时间槽为空，时间槽i为单位时间长度，结束于时刻i。我们按惩罚值单调递减的顺序处理所有任务。当处理任务aj时，如果存在不晚于aj的截止时间dj的空时间槽，则将aj分配到其中最晚的那个。如果不存在这样的时间槽，将aj分配到最晚的空时间槽。

a.证明：此算法总能得到最优解。

b.利用快速不相交集合森林来高效实现该算法。假定输入任务集合已经按惩罚值单调递减的顺序排序。分析实现程序的运行时间。

查看答案及解析