Python写出带期限作业排序问题
时间: 2024-02-09 16:38:31 浏览: 28
假设有n个作业,每个作业有一个截止期限d和一个完成时间t,完成该作业的收益为p。假设每个作业只能完成一次,且不能超时。如何安排作业才能获得最大收益?
一种贪心算法是按照截止期限从小到大排序,然后依次选择待完成的作业中收益最大的作业,如果该作业的完成时间超过了截止期限,则放弃该作业。
以下是Python实现:
```python
def job_sort(jobs):
"""
按照截止期限从小到大排序
"""
return sorted(jobs, key=lambda x: x[1])
def job_schedule(jobs):
"""
安排作业,返回最大收益
"""
jobs = job_sort(jobs)
n = len(jobs)
# 安排作业的列表,-1表示该时间点没有安排作业
schedule = [-1] * n
# 当前时间
cur_time = 0
# 已经完成的作业收益
total_profit = 0
for i in range(n):
# 选择收益最大的待完成作业
max_profit_job = max(jobs, key=lambda x: x[2] if x[0] > cur_time else 0)
if max_profit_job[0] > cur_time and max_profit_job[0] <= max_profit_job[1]:
# 作业完成时间在截止期限内
cur_time = max_profit_job[0]
total_profit += max_profit_job[2]
schedule[jobs.index(max_profit_job)] = cur_time
jobs.remove(max_profit_job)
return total_profit, schedule
```
其中,jobs是一个列表,每个元素是一个三元组,分别表示完成时间、截止期限和收益。函数job_sort按照截止期限从小到大排序,函数job_schedule依次选择待完成的作业中收益最大的作业,如果该作业的完成时间超过了截止期限,则放弃该作业,并返回最大收益和安排作业的列表。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)