小v上学,老师布置了n个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间和其逾期的扣分。请给出小v做作业的顺序,以便扣最少的分。
时间: 2024-05-13 14:17:11 浏览: 19
这是一个经典的贪心问题,我们可以将作业按照最后提交时间从小到大排序,然后依次选择最早结束的作业,直到所有作业都完成。
具体实现方法为,将每个作业表示为一个三元组 (deadline, score, index),其中 deadline 表示最后提交时间,score 表示逾期扣分,index 表示该作业的序号。然后按照 deadline 从小到大排序,然后依次选择最早结束的作业,并将其添加到结果列表中,同时更新当前的截止时间和总扣分。
以下是 Python 代码实现:
```python
def schedule_homework(n, homeworks):
# 按照最后提交时间从小到大排序
homeworks.sort(key=lambda x: x[0])
# 当前时间和总扣分
cur_time, total_penalty = 0, 0
# 结果列表
result = []
for i in range(n):
# 当前作业的最后提交时间和逾期扣分
deadline, penalty, _ = homeworks[i]
# 如果当前时间加上完成该作业所需时间不超过最后提交时间,则选择该作业
if cur_time + 1 <= deadline:
result.append(i)
cur_time += 1
total_penalty += penalty
return result, total_penalty
```
其中,n 表示作业数量,homeworks 是一个列表,其中每个元素是一个三元组 (deadline, score, index)。
该算法的时间复杂度为 O(nlogn),主要是排序的时间复杂度。