使用jupyter notebook假设有n个作业A= [a1,a2…ai…an]需要你在截止日期前完成。 工作分配ai= [durationi,deadlinei]需要工期I天才能完成,并且必须在deadline之前或当天完成。您一次只能做一项作业,并且只能开始一次下一项作业 当前任务已完成。假设你从第一天开始,执行一个有效的算法来找出你能完成的作业的最大数量。
时间: 2023-04-08 11:03:32 浏览: 85
我可以回答这个问题。这是一个经典的贪心算法问题,可以使用贪心算法来解决。首先,按照deadlinei从小到大对作业进行排序。然后,从第一天开始,依次遍历每个作业,如果当前时间加上工期小于等于该作业的deadline,则可以选择该作业,否则就跳过该作业。最后,统计选择的作业数量即可。
相关问题
使用jupyter notebook假设有n个作业A= [a1,a2…ai…an]需要在deadline前完成。 工作分配ai= [duration,deadline]需要duration天才能完成,并且必须在deadline之前或当天完成。一次只能做一项作业,并且只能开始一次下一项作业 当前任务已完成。假设从第一天开始,执行一个有效的算法来找出能完成的作业的最大数量。
这是一个技术问题,我可以回答。这个问题可以使用贪心算法来解决。首先,按照deadline从小到大对作业进行排序。然后,从第一天开始,对于每个作业,如果它的deadline在当前天数之后,就将它加入已完成的作业列表中,并将当前天数加上该作业的duration。如果它的deadline在当前天数之前,就跳过该作业。最后,返回已完成作业的数量即可。
使用jupyter notebook完成以下代码:假设有n个作业A= [a1,a2…ai…an]需要在deadline前完成。 工作分配ai= [duration,deadline]需要duration天才能完成,并且必须在deadline之前或当天完成。一次只能做一项作业,并且只能开始一次下一项作业 当前任务已完成。假设从第一天开始,执行一个有效的算法来找出能完成的作业的最大数量。
我可以回答这个问题。以下是使用Python实现的代码:
```python
def max_jobs(A):
# 按照deadline排序
A = sorted(A, key=lambda x: x[1])
# 初始化当前时间和完成的作业数量
curr_time = 0
num_jobs = 0
# 遍历所有作业
for job in A:
# 如果当前时间加上作业所需时间小于等于deadline,则可以完成该作业
if curr_time + job[0] <= job[1]:
curr_time += job[0]
num_jobs += 1
return num_jobs
```
这个算法的时间复杂度为O(nlogn),其中n是作业的数量。
阅读全文