本文涉及知识点

C++贪心 临项交换

LeetCode 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 <= 10⁵
1 <= actual​i <= minimumi <= 10⁴

C++贪心+临项交换

n = tasks.length
某方案的第i项和第i项目，消耗为a1,a2,需要m1,m2。交换两项对其它项无影响：
一，后面的项不影响前面的项，故前面i项目不受影响。
二，无论如何调整这两项的顺序，两项都消耗a1+a2。
当前方案：执行之前能量至少：max(m1,m2+a1)
交换后方案：执行之前至少：max(m2,m1+a2)
由于两个方案都不是可行解，无需要讨论，故至少有一个解合法。$\to$ 执行之前的能量 >= max(n1,n2)。
如果m2+a1 > m1+a2 ，则后执行a1 更优。
即m2-a2 > m1-a1，即小的后执行。
对task的下标indexs按 task[i][0]+task[i][1]的升序排序。
ans = INT_MIN
for i =indexs
ans = max(ans+task[i][1],task[i][0])

代码

核心代码

class Solution {
		public:
			int minimumEffort(vector<vector<int>>& tasks) {
				vector<int> indexs(tasks.size());
				iota(indexs.begin(), indexs.end(), 0);
				sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return tasks[i1][1] - tasks[i1][0] < tasks[i2][1] - tasks[i2][0]; });
				int ans = INT_MIN;
				for (int i : indexs) {
					ans = max(ans + tasks[i][0], tasks[i][1]);
				}
				return ans;
			}
		};

单元测试

vector<vector<int>> tasks;
		TEST_METHOD(TestMethod11)
		{
			tasks = { {1,2},{2,4},{4,8} };
			auto res = Solution().minimumEffort(tasks);
			AssertEx(8, res);
		}
		TEST_METHOD(TestMethod12)
		{
			tasks = { {1,3},{2,4},{10,11},{10,12},{8,9} };
			auto res = Solution().minimumEffort(tasks);
			AssertEx(32, res);
		}
		TEST_METHOD(TestMethod13)
		{
			tasks = { {1,7},{2,8},{3,9},{4,10},{5,11},{6,12} };
			auto res = Solution().minimumEffort(tasks);
			AssertEx(27, res);
		}