LeetCode 1665. 完成所有任务的最少初始能量
题目描述
题意分析
每个任务只有在当前能量至少为
minimum时才能开始，完成后实际扣除actual。任务可以重排，需要让完成全部任务所需的初始能量尽量小；题目保证actual <= minimum。
解法：贪心排序
核心思路
[!blue]
排序依据可以从相邻两个任务推出。设任务 $A$ 的消耗、门槛为 $(a,m_A)$，任务 $B$ 为 $(b,m_B)$。先做 $A$ 再做 $B$，开始这两个任务前至少需要 $E_{AB}=\max(m_A,a+m_B)$；反过来需要 $E_{BA}=\max(m_B,b+m_A)$。如果 $m_A-a\ge m_B-b$，移项得 $b+m_A\ge a+m_B$，同时因为 $b\ge0$，还有 $b+m_A\ge m_A$。因此 $E_{AB}\le b+m_A\le E_{BA}$，把
minimum - actual更大的任务放在前面，不会提高这两个任务的能量要求。交换前后，两个任务的总消耗都是 $a+b$，前面的任务和后面的剩余能量都不变。因此可以不断交换差值顺序颠倒的相邻任务，最终得到按
minimum - actual降序排列的全局最优顺序；差值相同时无需额外规定先后。顺序确定后，用
spent记录此前实际消耗。若初始能量为 $E$，当前任务开始前剩余 $E-spent$，必须满足 $E\ge spent+minimum$。取所有任务的这类约束的最大值，就是既必要又足够的初始能量。每轮先记录约束，再把当前actual累加到spent；由于actual <= minimum，成功启动也保证完成后能量不会为负。
解题步骤
- 按门槛与实际消耗之差降序排序。
- 初始化已消耗能量与答案。
- 先用 spent+minimum 更新答案，再增加 actual。
- 返回最大启动约束。
代码实现
class Solution {
public int minimumEffort(int[][] tasks) {
// 按启动门槛减实际消耗的差值降序排列。
Arrays.sort(tasks, (a, b) -> Integer.compare(b[1] - b[0], a[1] - a[0]));
int answer = 0;
int spent = 0;
for (int[] task : tasks) {
// 当前任务对初始能量的要求，还要加上此前实际消耗。
answer = Math.max(answer, spent + task[1]);
spent += task[0];
}
return answer;
}
}
import "sort"
func minimumEffort(tasks [][]int) int {
// 按启动门槛减实际消耗的差值降序排列。
sort.Slice(tasks, func(i, j int) bool {
left := tasks[i][1] - tasks[i][0]
right := tasks[j][1] - tasks[j][0]
return left > right
})
answer, spent := 0, 0
for _, task := range tasks {
// 当前任务对初始能量的要求，还要加上此前实际消耗。
if need := spent + task[1]; need > answer {
answer = need
}
spent += task[0]
}
return answer
}
复杂度分析
- 时间复杂度：$O(n\log(n+1))$，排序后线性扫描。
- 空间复杂度：扫描额外 $O(1)$；计入排序后，Java 最坏为 $O(n)$，Go 排序调用栈为 $O(\log n)$。输入会被重排。
关键点总结
[!green]
- 门槛是启动要求，实际消耗才从能量中扣除。
- 排序依据来自两任务交换，不是只比较门槛大小。
- 答案约束在累计当前消耗之前计算。
易错点总结
[!yellow]
- 差值按升序排列：把更需要保留能量的任务拖到后面。
- 用 minimum 累加 spent：误把门槛当成真实消耗。
- 只取所有门槛最大值：漏掉任务前已经消耗的能量。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 174. 地下城游戏 | 困难 | 只看总消耗不足以保证过程中资源不低于门槛，两题都要考虑最坏前缀需求。 |
| 1029. 两地调度 | 中等 | 同样通过交换论证推导两字段差值作为排序关键量，本题差值是最低门槛与实际消耗之差。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！