用贪心算法编程求解任务安排问题_swust oj: 71:task scheduling 一个单位时间任务是恰好需要一个单位时间完成

题目：用贪心算法编程求解以下任务安排问题

        一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时间任务的有限集S。关于S的一个时间表用于描述S中单位时间任务的执行次序。时间表中第1个任务从时间0 开始执行直至时间1 结束，第2 个任务从时间1 开始执行至时间2 结束，…，第n个任务从时间n-1 开始执行直至时间n结束。
具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下。
(1) n个单位时间任务的集合S={1,2,…,n}；
(2) 任务i的截止时间di ,1≤i≤n,1≤ di ≤n，即要求任务i在时间di 之前结束；
(3) 任务i的误时惩罚wi ,1≤i≤n,即任务i未在时间di 之前结束将招致wi 的惩罚；若按时完成则无惩罚。

已知：给定的n 个单位时间任务，各任务的截止时间di ,各任务的误时惩罚wi ,1≤i≤n，

要求：确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。

解析：任务调度问题

1. 按照任务的截止时间从小到大排序，即将任务按照最后期限从早到晚排列。
2. 依次考虑每个任务，若将该任务放在当前时间表的最早可用时间能使总误时惩罚减少，则将该任务放入时间表中。
3. 若将该任务放入时间表中会使总误时惩罚增加，则舍弃该任务。
4. 重复步骤2-3，直到所有任务都被考虑完毕。

优先安排截止时间更早的任务，以保证能够满足所有任务的期限要求；同时在可行的情况下，优先安排误时惩罚更高的任务，以最大程度地减少总误时惩罚。

贪心策略：

1. 按照任务的截止时间从小到大排序，即将任务按照最后期限从早到晚排列。
2. 依次考虑每个任务，若将该任务放在当前时间表的最早可用时间能使总误时惩罚减少，则将该任务放入时间表中。
3. 若将该任务放入时间表中会使总误时惩罚增加，则舍弃该任务。
4. 重复步骤2-3，直到所有任务都被考虑完毕。

优先安排截止时间更早的任务，以保证能够满足所有任务的期限要求；同时在可行的情况下，优先安排误时惩罚更高的任务，以最大程度地减少总误时惩罚。

实现：

def task_scheduling(tasks):
    # 按照截止时间将任务按照从小到大排序
    sorted_tasks = sorted(tasks, key=lambda x: x[1])
 
    # 初始化完成时间和总误时惩罚
    completion_time = 0
    total_penalty = 0
 
    # 初始化任务排列
    schedule = []
 
    for task in sorted_tasks:
        # 如果当前任务完成时间超过了它的截止时间，计算误时惩罚
        if completion_time > task[1]:
            total_penalty += task[2]
 
        # 更新完成时间为当前任务结束时间
        completion_time = max(completion_time, task[1]) + 1
 
        # 将当前任务添加到任务排列中
        schedule.append(task[0])
 
    return schedule, total_penalty
 
 
# 测试样例
tasks = [(1, 4, 70), (2, 2, 60), (3, 4, 50), (4, 3, 40), (5, 1, 30), (6, 4, 20)]
schedule, penalty = task_scheduling(tasks)
print("任务排列:", schedule)
print("总误时惩罚:", penalty)

      对于任务的排列，我们可以看到程序使用了贪心算法，按照任务的截止时间从小到大进行排序，并尽可能地将截止时间早的任务放在前面执行，这样可以最大限度地避免误时惩罚的产生。