题目描述
给你一个任务数组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 <= actual_i <= minimum_i <= 10^4
算法1
(贪心 青蛙跳) $O(nlog(n))$ // 生动形象,喜欢抽象的可以看算法2, 代码是一样的
- 假设我们有一只青蛙在井里,他一共有
n
个操作: 往上跳b
步,并且回落b - a
步最后停在a
处(即:实际跳了a
步),要求青蛙在n
步操作之后跳到井口,问井的最小高度是多少。 - 对应:
- 井的高度是能够完成任务的总能量。
- 每一个操作是一个任务。
- 每次跳的高度加上起跳时的高度是是井口的可能最低高度。
- 每次回落的高度是任务的实际消耗,因此每个任务执行完,总消耗应该是之前所有任务的
a
值的和。
- 因此对于每一步而言,井口的最低高度应该是 max(b, sum(pre_a) + a)
- 第
n
步执行完的最低高度即为答案. - 为了保证最低高度的递增,我们需要对每次实际能跳的高度(即
b-a
排序)。例如, 当第一步是 从井底跳到第5
层滑落到第2
层时,差值是3
。
算法2
(贪心) $O(nlog(n))$
- 假设我们的初始能量
ans
为0
, 即一个任务都不执行需要的能量是0
, 从0
开始累加,如果前i - 1
个任务需要耗费的能量总和都不如第i
个任务需要的最低能量的话, 更新能量为最低能量tasks[i][1]
,否则维持ans += tasks[i][0]
. - 由于对于每一个任务执行的时候,假设前面消耗的总能量
pre
,都必须有pre + tasks[i][0] >= tasks[i][1]
,即pre >= tasks[i][1] - tasks[i][0]
- 无论以何种顺序枚举
pre
最终都是sum(task[i][0])
- 因此我们考虑对
tasks[i][1] - tasks[i][0]
从小到大排序,令每一次的剩余能量都尽可能的取到最小.
时间复杂度
- 排序需要 $O(nlog(n))$ 的时间复杂度
- 枚举每一个任务的最小剩余能量和总能量需要$O(n)$的时间
- 故总时间复杂度为 $O(nlog(n))$
C++ 代码
class Solution {
public:
int minimumEffort(vector<vector<int>>& tasks) {
int n = tasks.size();
sort(tasks.begin(), tasks.end(), [&](vector<int>& t1, vector<int>& t2){
return t1[1] - t1[0] < t2[1] - t2[0];
});
int ans = 0;
for(int i = 0; i < n; i ++){
if (ans + tasks[i][0] < tasks[i][1]) ans = tasks[i][1];
else ans += tasks[i][0];
}
return ans;
}
};