算法中带时限的作业排序

带时限的作业排序是一种经典的贪心算法问题，也称为“最小惩罚排序”问题。该问题的描述如下：

有n个作业需要完成，每个作业有一个截止时间d和一个完成时间t。如果一个作业在截止时间d之前完成，则不会受到任何惩罚，否则将受到一个惩罚p，惩罚值为p×(完成时间-截止时间)。现在需要将这n个作业排序，使得总惩罚最小。

解决这个问题的贪心策略是按照截止时间递增的顺序对作业进行排序，然后依次完成作业。具体地，假设已经将作业排序后得到一个序列s，且完成前i个作业所需的时间为ti，则将第i+1个作业安排在ti最小的时间点完成。这个时间点应该满足两个条件：1）不晚于作业的截止时间；2）在之前的作业中没有被占用。

实现时，可以使用一个数组a来记录每个时间点的可用性，初始时a[i]=0表示i时刻可用，完成作业后将a[i]=1表示i时刻被占用。对于每个作业，从它的截止时间开始，逆序遍历数组a，找到第一个可用的时间点，将作业安排在这个时间点完成，同时更新a数组。完成所有作业后，将每个作业的惩罚值相加即可得到总惩罚。

下面是Python代码实现：

def job_sort(jobs):
jobs.sort(key=lambda x: x[1])
n = len(jobs)
a = [0] * (jobs[-1][1] + 1)
p = 0
for i in range(n):
d, t = jobs[i]
for j in range(d, -1, -1):
if a[j] == 0:
a[j] = 1
p += t * (j - d)
break
return p

jobs = [(2, 3), (1, 5), (4, 2), (5, 1), (3, 4)]
print(job_sort(jobs)) # 输出：18