郑州网站制作建设,php网站开发技术代码,丹东网站优化,正规的网站制作哪个好文章目录1. 题目2. 解题1. 题目
给你一个任务数组 tasks #xff0c;其中 tasks[i] [actuali, minimumi] #xff1a;
actuali 是完成第 i 个任务 需要耗费 的实际能量。minimumi 是开始第 i 个任务前需要达到的最低能量。
比方说#xff0c;如果任务为 [10, 12] 且你当…
文章目录1. 题目2. 解题1. 题目
给你一个任务数组 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-initial-energy-to-finish-tasks 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
差值大的优先满足
class Solution {
public:int minimumEffort(vectorvectorint tasks) {sort(tasks.begin(), tasks.end(),[](autoa, autob) {return a[1]-a[0] b[1]-b[0];//差值大的优先});int val 0, delta 0, sum 0;for(int i 0; i tasks.size(); i) sum tasks[i][0];//所有最少需要的消耗int s sum;for(int i 0; i tasks.size(); i) {if(s-tasks[i][1] 0){ //不能开启任务delta tasks[i][1]-s;//需要增加体力s tasks[i][1]-s;//增加体力}s - tasks[i][0];//做任务消耗体力了}return sumdelta;}
};988 ms 91.3 MB
优化一下
class Solution {
public:int minimumEffort(vectorvectorint tasks) {sort(tasks.begin(), tasks.end(),[](autoa, autob) {return a[1]-a[0] b[1]-b[0];//差值大的优先});int val 0, presum 0;for(int i 0; i tasks.size(); i) {val max(val, presumtasks[i][1]);presum tasks[i][0];//前缀最小消耗}return val;}
};916 ms 91.3 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
