LeetCode 1665. 完成所有任务的最少初始能量

2021-10-22 HGNULB 约 5 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1665. 完成所有任务的最少初始能量

题意分析

每个任务用两个数刻画：tasks[i][0] 是完成它实际消耗的能量，tasks[i][1] 是开始它之前手上必须达到的能量门槛。所有任务都要完成，顺序可以任意安排，问初始能量至少要多少。

最容易被忽略的是这两个数的关系：门槛不小于消耗，但通常严格大于。这意味着一个任务会「冻结」一部分能量——你必须先攒够门槛才能动手，可动手之后只花掉其中一部分，剩下的又回到手里。真正被永久扣掉的只有消耗值，而门槛只在那一瞬间起作用。

由此可以立刻算出答案的下界：所有消耗之和是必须付出的，一分都省不掉；同时任意单个任务的门槛也是下界之一。答案要同时不小于这两者，而且顺序会决定它比下界高出多少。

顺序为什么重要？因为总消耗是常量，与顺序无关，唯一受顺序影响的是「哪个时刻的门槛最难满足」。把「门槛远高于消耗」的任务留到最后做，那时手上的能量已经被前面的消耗掏空，就得预先多备一大笔；反过来先把它做掉，代价要小得多。

数据规模是 $10^5$ 个任务、能量值不超过 $10^4$。这个规模允许一次排序加一次扫描，但不允许任何两两比较的枚举。

边界包括：只有一个任务（答案就是它的门槛）；所有任务门槛等于消耗（答案就是消耗总和）；以及某个任务的门槛远超其他所有任务的总和。

解法：贪心排序

核心思路

设任务为 (actual, minimum)，差值 minimum - actual 表示执行前必须额外保留、执行后却不会消耗的能量。差值越大的任务越怕被前面的消耗拖累，应越早执行。

用相邻交换证明排序规则。设任务 A、B 的参数为 (a,mA)、(b,mB)。A 后接 B 时，进入这两项前至少需要
\[E_{AB}=\max(mA,a+mB)\]
B 后接 A 时需要
\[E_{BA}=\max(mB,b+mA)\]
若 mA - a >= mB - b，则 b + mA >= a + mB，并且 b + mA >= mA。因此 E_BA 不小于 E_AB 的两个候选项，得到 E_AB <= E_BA。所以差值更大的任务放前面不会更差；不断交换逆序相邻项，即得到按 minimum - actual 降序的全局最优顺序。

排序后扫描。spent 表示执行当前任务前已经消耗的总能量。要启动当前任务，初始能量至少为 spent + minimum；因此维护
\[answer=\max(answer,spent+minimum)\]
再令 spent += actual。不变量是：answer 始终等于已扫描任务所有启动约束的最大值，也就是完成此前任务所需的最小初始能量。

解题步骤

按 minimum - actual 从大到小排序。

初始化 spent = 0、answer = 0。

对每个任务，用 spent + minimum 更新初始能量下界，再把 actual 加入 spent。

返回所有启动约束中的最大值 answer。

[[1,2],[2,4],[4,8]] 的差值分别为 1、2、4，排序后为 [[4,8],[2,4],[1,2]]。三个启动约束依次是 8、8、8，所以答案为 8。若反向执行，最后启动 [4,8] 前已经消耗 3，需要初始能量 11。

当每个任务都满足 minimum == actual 时，差值全为 0，任意顺序都等价，答案就是总消耗。

代码实现

import java.util.Arrays;

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)$，排序占主导，扫描为 $O(n)$。

空间复杂度：扫描额外空间为 $O(1)$；计入标准库排序，Java 对对象数组最坏需要 $O(n)$ 辅助空间，Go 排序使用 $O(\log n)$ 栈空间。

关键点总结

排序键不能凭直觉猜，应通过相邻两任务的交换不等式推出。

minimum - actual 越大，任务越应提前执行。

spent + minimum 是当前任务对初始能量提出的准确下界。

answer 是所有已扫描启动约束的最大值，spent 是已发生的实际消耗。

输入顺序是 [actual, minimum]，两列不能读反。

易错点总结

按 minimum - actual 升序会把最需要保留能量的任务拖到后面。样例一会从 8 变为 11。

只按 minimum 或 actual 排序都缺少交换论证，不能保证最优。

把列读成 [minimum, actual] 会同时破坏排序键与能量约束。

更新答案时漏掉此前消耗 spent，会低估后续任务启动时所需的初始能量。

把 minimum 加入 spent 是错误的；任务完成后实际只消耗 actual。

相似题目

题目	难度	考察点
1005. K 次取反后最大化的数组和	简单	排序后逐个决策，但排序键就是元素本身，无需推导
134. 加油站	中等	同样在扫描中维护「累计余额」，但顺序被环形结构固定，考点是起点选择
1029. 两地调度	中等	排序键是两个方案的差值，与本题同源，但决策是二选一而非排先后
253. 会议室 II	中等	排序后用堆维护并发资源，答案是峰值而非累计补足量
621. 任务调度器	中等	顺序同样自由，但约束是相同任务的冷却间隔，答案由最高频次的填空公式给出
55. 跳跃游戏	中等	扫描中维护可达边界，是「维护一个随扫描更新的量」的最简形态，无排序环节
630. 课程表 III	困难	按截止时间排序后用大顶堆反悔，是贪心排序加反悔机制的组合，比本题多一层
1235. 规划兼职工作	困难	排序只是预处理，真正的决策要靠 DP 配合二分，说明排序未必能一路贪心到底