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

Raphael Liu Lv10

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

纯例子讲解帮助不太明白的人感受到其中的道理;

例1:【5,5】【5,7】

定义:minimum-actual越小的人称为越老实的人;反之,称为装逼人。
讲解: 显然【5,5】是个老实人,【5,7】是个装逼人。老实人很实在,最后剩下5给他,他就会欣然接受,不需要额外的需求,但是装逼人不一样,他明明只要5,确装逼说自己要7,这个时候怎么办呢,拿什么东西来装逼呢,只能借一下老实人的来装一下逼

我们明白,这个答案显然是10,装逼人【5,7】可以拿老实人的5给自己来装逼,所以在不改变结果的情况下他可以乱叫6,7,8,9,10,这些情况下答案都不会改变,一旦装逼人叫了【5,11】,就会发现老实人借给他的也不够他装逼了,无可奈何,我们只能给他分配额外资源让他装逼。

一旦相通这个之后,我们解题思路变成了:倒着安排,先把大量“老实人”放在前面把需求数字垫起来,这样后面的装逼人能装更大的逼,例2有两个老实人【5,5】【5,5】,装逼人就能叫道【5,15】,只要老实人还能借,他就还能装

下面的例子是举例让大家理解装逼程度一致,起始先后顺序是一样的
例3:【1,3】【3,5】 他们的老实程度一致 结果: 3(给第一个装逼) + 3(因为3+3>5) = 6 = 5(给第二个先装逼) + 1(5+ 1 > 3,够装逼了)

例4: 【1,4】【3,5】
大家自己思考一下这个就明白结果了,结果放在评论区,希望大家都能理解,喜欢的或者觉得有趣的不妨点个赞!!!!谢谢你们!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int minimumEffort(vector<vector<int>>& tasks) {//把握额外报的这部分如何让其无损
sort(tasks.begin(), tasks.end(), [&](vector<int> &a, vector<int> &b){
return a[1] - a[0] < b[1] - b[0];
});

int result = 0;

for (const auto &task: tasks){
result = max(result + task[0], task[1]);
}

return result;
}
};
 Comments
On this page
1665-完成所有任务的最少初始能量