)
【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 <= 1051 <= actuali<= minimumi<= 104
解题方法：贪心
单看每个task的第一个数actual，不论task顺序如何，actual之和都是需要被满足然后消耗掉的。单看这个，总能量至少为actual之和。
现在每个还多了个minimum。minimum这东西，不是实际消耗的能量，但是是启动这个任务所拥有的最少初始能量。minimum可能比actual多，并且这多出来的部分并不会被消耗。
多出来的部分被浪费了吗？不一定。你也可以把这多出来的部分用到其他任务上去。例如两个任务[ [ 3 , 3 ] , [ 1 , 4 ] ] [[3, 3], [1, 4]][[3,3],[1,4]]，第二个任务需要多出来3 33的能量，这3 33的能量正好全部用到第一个任务上，一点都不浪费。
也就是说，最佳策略是：优先完成多出来部分比较多的任务，然后把多出来的能量用到其他浪费更小的任务上去。
- 时间复杂度O ( n log n ) O(n\log n)O(nlogn)，其中n = l e n ( t a s k s ) n=len(tasks)n=len(tasks)
- 空间复杂度O ( log n ) O(\log n)O(logn)
AC代码
C++
/* * @LastEditTime: 2026-05-12 16:36:57 */classSolution{public:intminimumEffort(vector<vector<int>>&tasks){sort(tasks.begin(),tasks.end(),[](constvector<int>&a,constvector<int>&b){returna[1]-a[0]>b[1]-b[0];});intans=0,now=0;for(vector<int>&task:tasks){if(now<task[1]){intneed=task[1]-now;now=task[1];ans+=need;}now-=task[0];}returnans;}};#ifdef_DEBUG/* [[1,2],[2,4],[4,8]] 8 */intmain(){string s;while(cin>>s){vector<vector<int>>v=stringToVectorVector(s);Solution sol;cout<<sol.minimumEffort(v)<<endl;}return0;}#endif同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
