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

标签: 贪心 数组 排序

难度: Hard

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

Submission

运行时间: 127 ms

内存: 50.5 MB

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1] - x[0])
        ans = 0
        for a,b in tasks:
            ans = ans + a if ans+a >= b else b
        return ans

Explain

本题解采用贪心算法的思想。首先将任务按照 `minimum - actual` 的值升序排序，这样可以保证在完成每个任务时，剩余的能量尽可能多。在遍历排序后的任务时，如果当前能量加上当前任务的实际能量大于等于当前任务的最低能量，则可以完成该任务，剩余能量更新为当前能量加上实际能量；否则，说明当前能量不足以完成该任务，需要将初始能量增加到当前任务的最低能量。

时间复杂度: O(nlogn)

空间复杂度: O(1)

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1] - x[0])  # 按照 minimum - actual 升序排序
        ans = 0  # 初始能量
        for a, b in tasks:  # 遍历任务
            ans = ans + a if ans + a >= b else b  # 更新剩余能量或者初始能量
        return ans  # 返回最少初始能量

Explore

选择按 `minimum - actual` 的差值进行排序是为了优先处理那些对初始能量要求较高相对于实际消耗的任务。这种排序方式有助于尽早处理那些容易造成能量短缺的任务，从而在后续任务中保留更多的能量，减少总体所需的初始能量。如果单独按 `minimum` 或 `actual` 排序，可能导致处理某些任务时，尽管实际消耗较小，但由于最低能量要求高而不得不提前消耗大量能量，这不利于能量的有效分配和利用。

任务排序后的顺序确实影响最终的初始能量计算。由于算法总是尝试在当前能量下完成任务，若当前能量不足以满足任务的最低能量要求，则必须增加能量。排序方式决定了处理任务的顺序，从而影响何时需要增加能量及增加多少能量。按照 `minimum - actual` 排序有助于减少因任务顺序不合理导致的多次增加能量的情况，从而降低所需的初始能量。

实际上，在这种情况下，增加的能量计算考虑了已消耗的能量。如果当前能量加上实际能量不足以满足最低能量要求，算法直接将当前能量设置为该任务的最低能量要求，这意味着增加的能量正好是从当前能量到达最低能量所需的额外能量。这种方法确保了每个任务都能在最低能量要求下开始，并且累计的能量消耗是连续的，没有遗漏。

贪心策略在这个问题的上下文中是有效的，主要是因为任务的处理顺序关系到总体能量的最小初始配置。通过按 `minimum - actual` 的差值进行排序，我们已经在尝试将影响最大的任务优先处理，从而尽可能地减少了初始能量的总需求。在这种特定的排序和处理策略下，不太可能存在其他任务排序方式，使得贪心策略无法得到最优解。这种策略确保了每个步骤的局部最优决策能够达到全局最优解。