快捷搜索:

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

题目描述: 给你一个任务数组 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 <= actuali <= minimumi <= 104

方法1: 主要思路: (1)统计出完成任务实际需要的能量作为初始的能量值; (2)同时统计出每个任务需要的能量值和实际的能量值之差,同时记录其对应的索引,然后对该统计数组使用差值进行降序排序; (3)使用排序后的数组,拿出对应的索引作为完成任务时的顺序; (4)在该顺序下完成任务时,每次判断剩余的能量是否能够满足需要的能量,不能的话,就在初始值上增加对应的差值,并将当前能量置为需要的能量,直到完成所有的任务;

class Solution {
          
   
public:
    int minimumEffort(vector<vector<int>>& tasks) {
          
   
        vector<pair<int,int>> diff(tasks.size(),pair<int,int>(0,0));//统计需要的能量和实际的能量之差,并保存对应索引
        long long sum_all=0;//统计需要的能量,初始值统计为实际完成任务需要的能量之和
        for(int i=0;i<tasks.size();++i){
          
   
            diff[i]={
          
   tasks[i][1]-tasks[i][0],i};//差值
            sum_all+=tasks[i][0];//实际能量之和
        }
        //根据差值的大下,将数组进行降序排序
        sort(diff.begin(),diff.end(),[](auto& lhs,auto& rhs){
          
   
            return lhs.first>rhs.first;
        });
        long long tmp=sum_all;//辅助变量
        //按照排序后的差值数组的顺序,逐个的完成任务
        for(auto& it:diff){
          
   
            if(tmp<tasks[it.second][1]){
          
   //若当前剩余的能量小于需要的能量
                sum_all += tasks[it.second][1] - tmp;//在统计值上增加缺少的能量数
                tmp = tasks[it.second][1];//将当前剩余的能量值修改为需要的能量值
            }
            tmp-=tasks[it.second][0];//去除实际需要的能量值
        }
        return sum_all;
    }
};
经验分享 程序员 职场和发展