Hard

题目描述

给你一个任务数组 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

示例 3:

输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出：27

提示:

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

解题思路

这道题的关键在于找到最优的任务执行顺序，然后计算所需的最少初始能量。

思路分析：

  1. 贪心策略：我们需要找到一个排序策略，使得按这个顺序执行任务时，所需的初始能量最少。关键观察是任务的执行顺序会影响所需的初始能量。

  2. 排序规则：对于两个任务 A[actual_a, min_a] 和 B[actual_b, min_b]，我们应该优先执行哪一个？

    • 如果先执行A再执行B，需要的最小能量是 max(min_a, min_b + actual_a)
    • 如果先执行B再执行A，需要的最小能量是 max(min_b, min_a + actual_b)
    • 比较这两个值，选择较小的执行顺序
    • 化简后得到排序规则：按 (min_i - actual_i) 降序排列

  3. 计算初始能量：排序后从后往前计算，维护完成剩余任务所需的最小能量。对于每个任务，初始能量至少要满足：

    • 能够开始当前任务：>= min_i
    • 完成当前任务后能完成剩余任务：>= actual_i + 剩余任务所需能量

  4. 优化方法：也可以使用二分搜索，因为判断函数具有单调性。

推荐解法：贪心 + 排序，时间复杂度更优。

代码实现

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        // 按照 minimum - actual 降序排列
        sort(tasks.begin(), tasks.end(), [](const vector<int>& a, const vector<int>& b) {
            return (a[1] - a[0]) > (b[1] - b[0]);
        });
        
        int totalActual = 0;
        for (auto& task : tasks) {
            totalActual += task[0];
        }
        
        int need = 0;
        // 从后往前计算
        for (int i = tasks.size() - 1; i >= 0; i--) {
            need = max(need + tasks[i][0], tasks[i][1]);
        }
        
        return need;
    }
};

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        # 按照 minimum - actual 降序排列
        tasks.sort(key=lambda x: x[1] - x[0], reverse=True)
        
        need = 0
        # 从后往前计算
        for i in range(len(tasks) - 1, -1, -1):
            actual, minimum = tasks[i]
            need = max(need + actual, minimum)
        
        return need

public class Solution {
    public int MinimumEffort(int[][] tasks) {
        // 按照 minimum - actual 降序排列
        Array.Sort(tasks, (a, b) => (b[1] - b[0]).CompareTo(a[1] - a[0]));
        
        int need = 0;
        // 从后往前计算
        for (int i = tasks.Length - 1; i >= 0; i--) {
            int actual = tasks[i][0];
            int minimum = tasks[i][1];
            need = Math.Max(need + actual, minimum);
        }
        
        return need;
    }
}

var minimumEffort = function(tasks) {
    // 按照 minimum - actual 降序排列
    tasks.sort((a, b) => (b[1] - b[0]) - (a[1] - a[0]));
    
    let need = 0;
    // 从后往前计算
    for (let i = tasks.length - 1; i >= 0; i--) {
        const [actual, minimum] = tasks[i];
        need = Math.max(need + actual, minimum);
    }
    
    return need;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
贪心排序O(n log n)O(1)
二分搜索O(n² log(sum))O(1)

推荐解法：贪心排序，时间复杂度更优，实现简洁。