完成所有任务的最少初始能量
难度:
标签:
题目描述
代码结果
运行时间: 127 ms, 内存: 50.5 MB
// Java Stream Solution
// 思路:与Java解法类似,使用Stream API进行排序和遍历。
// 1. 使用Stream对任务按照所需最低能量排序。
// 2. 计算每个任务的能量差,
// 计算最小的初始能量,使得开始任务时能量大于等于任务所需最低能量。
import java.util.Arrays;
import java.util.stream.Stream;
public class StreamSolution {
public int minimumEffort(int[][] tasks) {
// 将任务转换为Stream并排序
int[][] sortedTasks = Stream.of(tasks)
.sorted((a, b) -> b[1] - a[1])
.toArray(int[][]::new);
int initialEnergy = 0;
int currentEnergy = 0;
// 逆序完成任务
for (int[] task : sortedTasks) {
if (currentEnergy < task[1]) {
initialEnergy += task[1] - currentEnergy;
currentEnergy = task[1];
}
currentEnergy -= task[0];
}
return initialEnergy;
}
}
解释
方法:
本题解采用贪心算法的思想。首先将任务按照 `minimum - actual` 的值升序排序,这样可以保证在完成每个任务时,剩余的能量尽可能多。在遍历排序后的任务时,如果当前能量加上当前任务的实际能量大于等于当前任务的最低能量,则可以完成该任务,剩余能量更新为当前能量加上实际能量;否则,说明当前能量不足以完成该任务,需要将初始能量增加到当前任务的最低能量。
时间复杂度:
O(nlogn)
空间复杂度:
O(1)
代码细节讲解
🦆
为何选择按 `minimum - actual` 的差值进行排序,而不是单独按 `minimum` 或 `actual` 排序?
▷🦆
在实现中,任务排序后的顺序影响最终的初始能量计算吗?如果影响,为什么?
▷🦆
你在解释中提到,如果当前能量加上实际能量不足以满足最低能量要求,就需要增加到当前任务的最低能量。这种情况下,实际上增加的能量是否正确地计算了已消耗的能量?
▷🦆
解法中提到的贪心策略是否在所有情况下都是有效的?有没有可能存在某种任务排序,使得贪心策略无法得到最优解?
▷