使用jupyter notebook以及贪心算法完成以下代码:假设有n个作业A= [a1,a2…ai…an]需要在deadline前完成。 工作分配ai= [duration,deadline]需要duration天才能完成,并且必须在deadline之前或当天完成。一次只能做一项作业,并且只能开始一次下一项作业 当前任务已完成。假设从第一天开始,执行一个有效的算法来找出能完成的作业的最大数量。
时间: 2023-04-08 19:03:36 浏览: 105
贪心算法(算法)-代码
以下是使用贪心算法的代码:
```python
def max_jobs(A):
# 按照deadline排序
A = sorted(A, key=lambda x: x[1])
n = len(A)
# 初始化可完成的作业数量和当前时间
count = 0
time = 0
for i in range(n):
# 如果当前时间加上该作业的duration小于等于deadline,则可以完成该作业
if time + A[i][0] <= A[i][1]:
count += 1
time += A[i][0]
return count
```
使用该函数,可以得到能完成的作业的最大数量。例如:
```python
A = [[2, 5], [1, 2], [3, 7], [2, 4], [1, 5]]
print(max_jobs(A)) # 输出3
```
该算法的时间复杂度为O(nlogn),其中n为作业的数量。
阅读全文