Minimum Initial Energy to Finish Tasks

Master this topic with zero to advance depth.

Minimum Initial Energy to Finish Tasks

You are given an array tasks where tasks[i] = [actual_i, minimum_i]:

actual_i is the actual amount of energy you spend to finish the $i^{th}$ task.
minimum_i is the minimum amount of energy you need to begin the $i^{th}$ task.

You can finish the tasks in any order. Return the minimum initial amount of energy you need to finish all tasks.

Visual Representation

Tasks: [[1, 3], [2, 4], [10, 11]]

Optimal Order: Sort by (minimum - actual) descending.
1. [1, 3]: diff 2
2. [2, 4]: diff 2
3. [10, 11]: diff 1

Simulation starting with 14:
[1, 3]: 14 >= 3. Spend 1. Left 13.
[2, 4]: 13 >= 4. Spend 2. Left 11.
[10,11]: 11 >= 11. Spend 10. Left 1.
Result: 14

Hard

Examples

Input: tasks = [[1,3],[2,4],[10,11]]
Output: 14
Starting with 14 energy: finish [1,3] (left 13), [2,4] (left 11), [10,11] (left 1).

Approach 1

Level I: Brute Force (All Permutations)

Intuition

Since we can finish tasks in any order, we can try all $N!$ permutations of tasks. For each permutation, we calculate the minimum initial energy required to complete the tasks in that specific order. The answer is the minimum of these values.

Thought Process

Generate all $N!$ permutations of tasks.
For each permutation:
- Start with current energy $E = 0$ (working backwards) or try binary search on initial energy.
- Simpler: starting backwards from the last task, energy = max(min_i, energy + actual_i).
Return the minimum energy found across all permutations.

Pattern: Brute Force / Permutations

⏱ O(N! * N) - Factorial number of permutations.💾 O(N) for recursion stack.

java

import java.util.*;

public class Main {
    public static int minimumEffort(int[][] tasks) {
        // To find all permutations and get the minimum, the logic would be complex.
        // A simpler way: try all permutations using recursion.
        return -1; // Placeholder for brute force logic
    }

    public static void main(String[] args) {
        System.out.println("Brute force tries all N! orders of tasks.");
    }
}

Approach 2

Level II: Binary Search on Initial Energy

Intuition

If we can finish the tasks with initial energy E, then we can also finish them with any energy E' > E. This monotonicity allows us to binary search for the minimum energy. However, even with binary search, we still need a greedy order to verify feasibility efficiently.

Thought Process

Search range: [sum(actual), 10^9].
canFinish(energy): Try a greedy order (e.g., sort by minimum - actual desc) and see if the tasks are completed.
If canFinish(mid) is true, try smaller; else try larger.

Pattern: Binary Search on Answer

⏱ O(N log N + N log MaxSum).💾 O(1).

Detailed Dry Run

Try Energy 14 for [[1,3],[2,4],[10,11]]

Task [1,3]: 14 >= 3. Spend 1. Left 13.
Task [2,4]: 13 >= 4. Spend 2. Left 11.
Task [10,11]: 11 >= 11. Spend 10. Left 1. True. Try Energy 13...

java

public class Solution {
    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));
        int l = 0, r = 1000000000, ans = r;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (check(mid, tasks)) { ans = mid; r = mid - 1; }
            else l = mid + 1;
        }
        return ans;
    }
    private boolean check(int energy, int[][] tasks) {
        for (int[] t : tasks) {
            if (energy < t[1]) return false;
            energy -= t[0];
        }
        return energy >= 0;
    }
}

Approach 3

Level III: Optimal Greedy (Sorting)

Intuition

To minimize initial energy, we want to perform tasks that 'save' the most energy requirement for later. The 'saved' energy after a task is $(minimal - actual)$ . Sorting tasks by this difference in descending order ensures we handle the most restrictive tasks (relative to their cost) while we have the most energy.

Thought Process

Sort tasks by (minimum - actual) descending.
Work backwards: Start with 0 energy. For each task, you must have at least m energy, so energy = max(m, energy + a).
Alternatively, work forwards: Keep track of totalEnergy needed and currentEnergy available.

Pattern: Greedy Sorting

⏱ O(N log N) for sorting.💾 O(1) if sorting in place.

Detailed Dry Run

tasks = [[1,3],[2,4],[10,11]] Sorted by (m-a) desc: [1,3] (2), [2,4] (2), [10,11] (1)

Task	Actual	Minimal	New Energy Needed
[10,11]	10	11	max(11, 0+10) = 11
[2,4]	2	4	max(4, 11+2) = 13
[1,3]	1	3	max(3, 13+1) = 14

java

import java.util.*;

public class Main {
    public static int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));
        int effort = 0, current = 0;
        for (int[] task : tasks) {
            if (current < task[1]) {
                effort += task[1] - current;
                current = task[1];
            }
            current -= task[0];
        }
        return effort;
    }

    public static void main(String[] args) {
        System.out.println(minimumEffort(new int[][]{{1,3},{2,4},{10,11}})); // 14
    }
}

← Previous QuestionHand of Straights

Next Question →Maximum Number of Events That Can Be Attended

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.