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

问题描述#

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

actual_i 是完成第 i 个任务 需要耗费 的实际能量。
minimum_i 是开始第 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 <= minimum_i <= 10⁴

解题思路#

思考 1

对于 \(\text{tasks}[i] = [\text{actual}_i, \text{minimum}_i]\) 和 \(\text{tasks}[j] = [\text{actual}_j, \text{minimum}_j]\)，

先后完成任务 \(i,j\)，所耗费的总能量为 \(\text{minimum_i} + \text{minimum_j} - \underbrace{(\text{minimum_i}-\text{actual_i})}_{\text{remainder}}\)
先后完成任务 \(j,i\)，所耗费的总能量为 \(\text{minimum_j} + \text{minimum_i} - \underbrace{(\text{minimum_j}-\text{actual_j})}_{\text{remainder}}\)

可以看出，如果上一次剩余的能量 \(\text{remainder}\) 越多，完成两个任务耗费的总能量最少。

思考 2

假设到 \(\text{tasks}[i]\) 时，如果已经耗费了 \(\text{ans}\) 个能量，还剩余 \(\text{remainder}\) 个能量，那么：

如果 \(\text{minimum}_i \le \text{remainder}\)，则说明之前的剩余可以到达该任务，此时有 \(\text{ans}=\text{ans},\text{remainder} = \text{remainder} - \text{actual}_i\)
如果 \(\text{minimum}_i \gt \text{remainder}\)，则说明还需要补上 \(\text{extra}=\text{minimum}_i - \text{remainder}\) 个能量才能到达该任务，此时有 \(\text{ans}=\text{ans}+\text{extra},\text{remainder} = \text{minimum}_i - \text{actual}_i\)

综上所述，按照 思考 1 ，我们需要先按照单独完成每个任务所剩余的能量进行降序排列，然后按照 思考 2 进行迭代即可。

排序

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[0] - x[1])  # 按照单独完成任务的剩余能量降序排列

        ans = 0
        remainder = 0

        for actual, minimum in tasks:
            if minimum <= remainder:
                remainder -= actual
            else:
                ans += minimum - remainder
                remainder = minimum - actual
        return ans

优先队列

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        hq = [(actual - minimum, actual, minimum) for actual, minimum in tasks]
        heapq.heapify(hq)

        ans = 0
        remainder = 0

        while hq:
            _, actual, minimum = heapq.heappop(hq)
            if minimum <= remainder:
                remainder -= actual
            else:
                ans += minimum - remainder
                remainder = minimum - actual
        return ans

测试数据

solution = Solution()

tasks = [[1, 2], [1, 7], [2, 3], [5, 9], [2, 2]]
assert solution.minimumEffort(tasks) == 11

tasks = [[1, 1], [1, 3]]
assert solution.minimumEffort(tasks) == 3

tasks = [[1, 2], [2, 4], [4, 8]]
assert solution.minimumEffort(tasks) == 8

tasks = [[1, 3], [2, 4], [10, 11], [10, 12], [8, 9]]
assert solution.minimumEffort(tasks) == 32

tasks = [[1, 7], [2, 8], [3, 9], [4, 10], [5, 11], [6, 12]]
assert solution.minimumEffort(tasks) == 27

print("PASS!")

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

问题描述#

解题思路#

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