How to Solve Minimum Initial Energy to Finish Tasks

Start by sorting tasks by the difference between minimum and actual energy in descending order to prioritize demanding tasks. Use a binary search over possible initial energies to validate the greedy sequence. This guarantees the minimal starting energy while ensuring that the invariant condition for task execution is never violated.

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 <= actual​i <= 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

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.

How GhostInterview Helps

• Provides immediate minimal-energy calculation using greedy sorting plus validation.
• Simulates candidate binary search efficiently on energy thresholds.
• Highlights energy invariants and edge cases to prevent misordering errors.

Topic Pages

• Array
• Greedy
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.