1665.完成所有任务的最少初始能量：排序(贪心)

【LetMeFly】1665.完成所有任务的最少初始能量：排序(贪心)

力扣题目链接：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 <= 105
• 1 <= actual​i <= minimumi <= 104

解题方法：贪心

单看每个task的第一个数actual，不论task顺序如何，actual之和都是需要被满足然后消耗掉的。单看这个，总能量至少为actual之和。

现在每个还多了个minimum。minimum这东西，不是实际消耗的能量，但是是启动这个任务所拥有的最少初始能量。minimum可能比actual多，并且这多出来的部分并不会被消耗。

多出来的部分被浪费了吗？不一定。你也可以把这多出来的部分用到其他任务上去。例如两个任务$[[3, 3], [1, 4]]$，第二个任务需要多出来$3$的能量，这$3$的能量正好全部用到第一个任务上，一点都不浪费。

也就是说，最佳策略是：优先完成多出来部分比较多的任务，然后把多出来的能量用到其他浪费更小的任务上去。

• 时间复杂度$O(n\log n)$，其中$n=len(tasks)$
• 空间复杂度$O(\log n)$

AC代码

C++

/*
 * @LastEditTime: 2026-05-12 16:36:57
 */
class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] - a[0] > b[1] - b[0];
        });
        int ans = 0, now = 0;
        for (vector<int>& task : tasks) {
            if (now < task[1]) {
                int need = task[1] - now;
                now = task[1];
                ans += need;
            }
            now -= task[0];
        }
        return ans;
    }
};

#ifdef _DEBUG
/*
[[1,2],[2,4],[4,8]]

8
*/
int main() {
    string s;
    while (cin >> s) {
        vector<vector<int>> v = stringToVectorVector(s);
        Solution sol;
        cout << sol.minimumEffort(v) << endl;
    }
    return 0;
}
#endif

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源