What is the core pattern in Minimum Initial Energy to Finish Tasks?

The pattern is greedy choice with invariant validation: sort tasks by (minimum - actual) descending and ensure current energy >= task minimum.

Why use binary search for initial energy?

The function f(x) = can you finish all tasks with x energy is monotonic, so binary search quickly finds the minimal valid starting energy.

Can tasks be completed in any order?

Yes, the problem allows reordering tasks to minimize starting energy, but the greedy ordering is optimal for this pattern.

What is a common mistake when simulating tasks?

Ignoring the invariant that current energy >= task minimum can cause an incorrect energy calculation.

How to handle large task arrays efficiently?

Sort once by (minimum - actual) and use binary search over initial energy instead of checking all permutations, reducing time complexity.

#1665

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个任务数组 tasks ，其中 tasks[i] = [actual i , minimum i ] ： actual i 是完成第 i 个任务需要耗费的实际能量。 minimum i 是开始第 i 个任务前需要达到的最低能量。比方说，如果任务为 [10, 12] 且你当前的能量为 11…

数组贪心排序

题目描述

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

lightbulb

解题思路

方法一：贪心 + 自定义排序

我们假设任务数为 $n$ ，初始能量值为 $E$ ，考虑完成最后一个任务，这需要我们完成前 $n-1$ 个任务后，剩余的能量值不小于完成最后一个任务需要达到的能量值 $m_n$ ，即：

E-\sum_{i=1}^{n-1} a_i \geq m_n

我们可以将 $m_n$ 表示成 $a_n+(m_n - a_n)$ ，然后将上面的式子变形，得到：

E-\sum_{i=1}^{n-1} a_i \geq a_n+(m_n - a_n)

整理可得：

E \geq \sum_{i=1}^{n} a_i + (m_n - a_n)

其中 $\sum_{i=1}^{n} a_i$ 是固定不变的，要使得初始值能量值 $E$ 最小，我们需要让 $m_n - a_n$ 最小，即 $a_n-m_n$ 最大。

因此，我们可以将任务按照 $a_i-m_i$ 从小到大排序。然后从前往后遍历任务，对于每个任务，如果当前能量值 $cur$ 小于 $m_i$ ，则需要增加能量值 $m_i - cur$ ，使得当前能量值刚好等于 $m_i$ ，然后再完成任务，更新 $cur = cur - a_i$ 。继续遍历，直到完成所有任务，即可得到初始所需的最少能量值。

时间复杂度 $O(n\times \log n)$ 。其中 $n$ 为任务数。忽略排序的空间开销，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        ans = cur = 0
        for a, m in sorted(tasks, key=lambda x: x[0] - x[1]):
            if cur < m:
                ans += m - cur
                cur = m
            cur -= a
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log n) for sorting plus O(n log m) for binary search validation, where n is the number of tasks and m is the maximum minimum requirement. Space complexity is O(1) extra or O(n) if storing a sorted copy.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looks for understanding of greedy ordering and energy invariant.
question_mark
Checks if candidate recognizes monotonic property for binary search over initial energy.
question_mark
May probe edge cases with tasks having high minimum minus actual values.

warning

常见陷阱

外企场景

error
Not sorting tasks correctly by (minimum - actual) can cause failure in minimal energy calculation.
error
Simulating without invariant checks may overestimate possible sequences.
error
Assuming sequential task input order instead of considering optimal permutations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Tasks with large differences between minimum and actual values.
arrow_right_alt
Tasks where all minimums are equal but actuals vary.
arrow_right_alt
Tasks with very high task count to test binary search efficiency.

help

常见问题

外企场景

继续练习

#1648 销售价值减少的颜色球 #1686 石子游戏 VI #1710 卡车上的最大单元数