#1665

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Initial Energy to Finish Tasks

Determine the minimum initial energy needed to finish all tasks using a greedy ordering based on required versus actual energy.

array greedy sorting

Problem Statement

You are given an array tasks where each task is represented as [actual, minimum]. To start a task, your current energy must be at least the task's minimum requirement. Completing the task reduces your energy by the task's actual value. You can choose the order of tasks freely, and your goal is to determine the smallest initial energy that allows all tasks to be completed.

For example, if a task is [10,12] and your current energy is 11, you cannot start it. If your energy is 13, you can complete it and your energy decreases to 3. Return the minimal starting energy that guarantees completion of all tasks.

Examples

Example 1

Input: tasks = [[1,2],[2,4],[4,8]]

Output: 8

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

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

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 Approach

Greedy Task Ordering

Sort tasks by (minimum - actual) descending to handle high-demand tasks first. This ordering ensures that the largest energy gap tasks are handled while energy is sufficient.

Binary Search Validation

Use binary search on possible initial energy values. For each candidate energy, simulate the greedy task order and check if energy never falls below the required minimum.

Invariant Checking

During simulation, maintain the invariant that current energy must always be >= task minimum. This guarantees that the chosen initial energy is sufficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Greedy + Custom Sorting

Assume the number of tasks is $n$ and the initial energy level is $E$. Consider completing the last task. This requires that after completing the first $n-1$ tasks, the remaining energy level is not less than the energy level required to complete the last task $m_n$, i.e.,

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#1648 sell diminishing valued colored balls #1686 stone game vi #1710 maximum units on a truck