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

greedy, https://leetcode.cn/problems/minimum-initial-energy-to-finish-tasks/

给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：

actuali 是完成第 i 个任务 需要耗费 的实际能量。
minimumi 是开始第 i 个任务前需要达到的最低能量。

比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。

请你返回完成所有任务的最少初始能量。

示例 1：

输入：tasks = [[1,2],[2,4],[4,8]]
输出：8
解释：
一开始有 8 能量，我们按照如下顺序完成任务：
    - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
    - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
    - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。

示例 2：

输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
输出：32
解释：
一开始有 32 能量，我们按照如下顺序完成任务：
    - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
    - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
    - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
    - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
    - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。

示例 3：

输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出：27
解释：
一开始有 27 能量，我们按照如下顺序完成任务：
    - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
    - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
    - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
    - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
    - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
    - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。

提示：

1 <= tasks.length <= 10^5
1 <= actuali <= minimumi <= 10^4

这道题目是一个经典的贪心算法问题。

解题思路

分析任务要求：每个任务有两个属性：actual（实际消耗）和 minimum（启动所需的最低能量）。完成一个任务后，你的能量会减少 actual。但在开始任务前，你必须拥有至少 minimum 的能量。
贪心策略确定：我们需要确定完成任务的最佳顺序。假设有两个任务 $A (a_{1}, m_{1})$ 和 $B (a_{2}, m_{2})$ 。
- 顺序 A -> B：起码需要能量 $m_{1}$ 。完成 A 后剩余 $E - a_{1}$ ，需满足 $E - a_{1} \geq m_{2}$ ，即 $E \geq a_{1} + m_{2}$ 。总初始能量需满足： $E \geq max (m_{1}, a_{1} + m_{2})$ 。
- 顺序 B -> A：同理，总初始能量需满足： $E^{'} \geq max (m_{2}, a_{2} + m_{1})$ 。
我们希望选择一种顺序，使得所需的初始能量更小。考虑差值 $d_{i} = m_{i} - a_{i}$ （即启动任务所需的“额外”缓冲能量）。直观上，缓冲能量需求越大的任务应该越先执行。因为先执行这些任务时，我们拥有的剩余总能量较多，更容易满足其高额的启动门槛，且这些缓冲能量在任务完成后可以被后续任务继续“复用”。
数学证明：比较 $max (m_{1}, a_{1} + m_{2})$ 和 $max (m_{2}, a_{2} + m_{1})$ 。将其展开为 $d_{i}$ ： $max (a_{1} + d_{1}, a_{1} + a_{2} + d_{2})$ 对比 $max (a_{2} + d_{2}, a_{2} + a_{1} + d_{1})$ 显然，若 $d_{1} > d_{2}$ ，则 $a_{1} + a_{2} + d_{1}$ 是这四个项中最大的。在“B -> A”的组合中， $a_{1} + a_{2} + d_{1}$ 必然是结果；而在“A -> B”中，最大的项仅为 $a_{1} + d_{1}$ 或 $a_{1} + a_{2} + d_{2}$ ，这两者都小于 $a_{1} + a_{2} + d_{1}$ 。因此，按照 $m_{i} - a_{i}$ 从大到小排序是最优的。

算法步骤

将 tasks 按照 minimum - actual 的差值从大到小进行排序。
遍历排序后的任务，计算维持任务链所需的最小初始能量。
- 设 ans 为当前所需的最小初始能量。
- 设 sum_actual 为当前已经消耗掉的能量总和。
- 对于每个任务 (actual, minimum)，为了能开始这个任务，初始能量必须满足： $a n s \geq s u m_a c t u a l + m i n i m u m$ 。
- 不断更新 ans = max(ans, sum_actual + minimum)。
最后返回 ans。

Python 代码实现

python

from typing import List

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        # 贪心策略：按照 (minimum - actual) 的差值从大到小排序
        # 差值越大，代表该任务对“启动门槛”的要求相对于“实际消耗”越高
        tasks.sort(key=lambda x: x[1] - x[0], reverse=True)
        
        ans = 0          # 记录最终需要的最小初始能量
        sum_actual = 0   # 记录之前所有任务消耗掉的能量总和
        
        for actual, minimum in tasks:
            # 对于当前任务，初始能量必须至少能支撑到：
            # 消耗完之前的任务后，剩下的能量还够这个任务的启动门槛 (minimum)
            # 即 ans - sum_actual >= minimum  =>  ans >= sum_actual + minimum
            if sum_actual + minimum > ans:
                ans = sum_actual + minimum
            
            # 累加当前任务的实际消耗
            sum_actual += actual
            
        return ans

复杂度分析

时间复杂度： $O (N \log N)$ ，其中 $N$ 是任务的数量，主要消耗在排序上。
空间复杂度： $O (1)$ 或 $O (N)$ ，取决于排序函数的空间开销。

T1665.完成所有任务的最少初始能量 ​

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