Skip to content

贪心

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

给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：

  • \(actual_i\) 是完成第 \(i\) 个任务 需要耗费 的实际能量。
  • \(minimum_i\) 是开始第 \(i\) 个任务前需要达到的最低能量。

比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。请你返回完成所有任务的 最少 初始能量。 \(1\le tasks.length \le 10^5, 1\le actual_i \le minimum_i \le 10^4\)

方法一

令 \(\textit{sum} = \sum \textit{actual}_i\)，答案一定大于等于 sum。令 \(cur = sum\)，随便按照某种交易顺序去进行，可能会遇到 \(\textit{cur} \lt \textit{minimum}_i\) 的情况，这时需要额外补充 \(\textit{minimum}_i - cur\) 份初始能量。

又因为 \(cur \ge \textit{actual}_i\) 是一定满足的，并且随着交易的进行，能量会逐渐递减，对后续的交易 \(\textit{minimum}_i\) 会更加不容易去满足。一个交易的难度定义为 \(\textit{minimum}_i - \textit{actual}_i\)，容易想到，这个值越大，该交易越难完成，越应该放在前面。

所以，我们按照 \(\textit{minimum}_i - \textit{actual}_i\) 从大到小排序，按照顺序去处理这些交易即可。

时间复杂度为 \(O(n\log n)\)。

更加详细的贪心正确性证明请参考：正确性证明

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [&](const vector<int>& lth, const vector<int>& rth) {
            return lth[1] - lth[0] > rth[1] - rth[0];
        });
        int sum = 0, res = 0;
        for (auto &v : tasks) sum += v[0];
        res = sum;
        for (auto &v : tasks) {
            if (sum < v[1]) {
                res += v[1] - sum;
                sum = v[1];
            }
            sum -= v[0];
        }
        return res;
    }
};
本文访问 次