You are given an array tasks
where tasks[i] = [actuali, minimumi]
:
actuali
is the actual amount of energy you spend to finish theith
task.minimumi
is the minimum amount of energy you require to begin theith
task.
For example, if the task is [10, 12]
and your current energy is 11
, you cannot start this task. However, if your current energy is 13
, you can complete this task, and your energy will be 3
after finishing it.
You can finish the tasks in any order you like.
Return the minimum initial amount of energy you will need to finish all the tasks.
Example 1:
Input: tasks = [[1,2],[2,4],[4,8]] Output: 8 Explanation: Starting with 8 energy, we finish the tasks in the following order: - 3rd task. Now energy = 8 - 4 = 4. - 2nd task. Now energy = 4 - 2 = 2. - 1st task. Now energy = 2 - 1 = 1. Notice that even though we have leftover energy, starting with 7 energy does not work because we cannot do the 3rd task.
Example 2:
Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]] Output: 32 Explanation: Starting with 32 energy, we finish the tasks in the following order: - 1st task. Now energy = 32 - 1 = 31. - 2nd task. Now energy = 31 - 2 = 29. - 3rd task. Now energy = 29 - 10 = 19. - 4th task. Now energy = 19 - 10 = 9. - 5th task. Now energy = 9 - 8 = 1.
Example 3:
Input: tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]] Output: 27 Explanation: Starting with 27 energy, we finish the tasks in the following order: - 5th task. Now energy = 27 - 5 = 22. - 2nd task. Now energy = 22 - 2 = 20. - 3rd task. Now energy = 20 - 3 = 17. - 1st task. Now energy = 17 - 1 = 16. - 4th task. Now energy = 16 - 4 = 12. - 6th task. Now energy = 12 - 6 = 6.
Constraints:
1 <= tasks.length <= 105
1 <= actuali <= minimumi <= 104
Solution: Greedy + Binary Search
Sort tasks by actual – min in ascending order, this will be the order we finish those tasks. Use binary search to check whether a given initial energy works or not. Note, the binary search part is unnecessary.
Time complexity: O(nlogn + nlogk)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int minimumEffort(vector<vector<int>>& tasks) { sort(begin(tasks), end(tasks), [](const auto& t1, const auto& t2) { return t1[0] - t1[1] < t2[0] - t2[1]; }); int l = tasks[0][1], r = INT_MAX - 1; auto check = [&](int cur) { for (const auto& task : tasks) { if (task[1] > cur) return false; cur -= task[0]; } return true; }; while (l < r) { const int m = l + (r - l) / 2; check(m) ? r = m : l = m + 1; } return l; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment