活动或任务计划问题 _贪婪算法

这是在单个处理器上最佳安排单位时间任务的争议, 其中每个作业都有最后期限, 如果错过了最后期限, 则必须支付罚款。
单位时间任务是一项工作, 例如要在计算机上紧急运行的程序, 而该程序恰好需要一个单位时间才能完成。给定单位任务的有限集合S, S的时间表是S的排列, 指定执行这些任务的顺序。计划中的第一个任务在时间0开始, 在时间1结束；第二个任务在时间1开始, 在时间2完成, 依此类推。
为每个处理器安排带有期限和罚款的单位时间任务的争议有以??下输入：

n个单位时间任务的集合S = {1, 2, 3 … .. n}。
一组n个整数截止期限d1 d2 d3 … dn, 使得di满足1≤di≤n, 并且任务i应该在时间di之前完成
一组n个非负权重或罚分w1 w2 … . wn, 这样, 如果任务i在时间di之前未完成, 我们将受到wi的惩罚, 而如果任务在其截止日期之前完成, 我们将不会受到惩罚。

在这里, 我们找到了S的时间表, 该时间表可最大程度地减少因错过截止日期而产生的总罚款。
如果任务在截止日期之后完成, 则它在此计划中延迟。否则, 任务将排在计划的早期。可以将任意计划始终以早期优先的形式放置, 在该形式中, 第一个任务优先于后一个任务, 即, 如果某个新任务x在某个后任务y之后, 则我们可以切换x和y的位置而不会影响x被早或晚。
总是可以将任意计划安排成规范的形式, 在该形式中, 第一个任务优先于后一个任务, 并且第一个任务按截止日期的顺序递减。
如果存在特定任务的计划, 则任务A的任务是独立的, 这样就不会延迟任务。因此, 计划的第一组任务形成一个独立的任务集“ l”, 表示所有独立的任务集。
对于任何任务集A, 如果t = 0、1、2 … .. n, 则A是独立的, 我们有Nt（A）≤t, 其中Nt（A）表示A的任务数为t或优先, 即如果预期A中的任务按截止时间单调增长的顺序进行, 则没有任务迟到。
示例：在给定的权重（罚款）和截止日期下, 找到以下任务的最佳计划。