# Minimum Initial Energy to Finish Tasks
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-initial-energy-to-finish-tasks)
Canonical: https://scaleengineer.com/dsa/problems/minimum-initial-energy-to-finish-tasks
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
You are given an array `tasks` where `tasks[i] = [actuali, minimumi]`:

* `actuali` is the actual amount of energy you **spend to finish** the `ith` task.
* `minimumi` is the minimum amount of energy you **require to begin** the `ith` task.

For example, if the task is `[10, 12]` and your current energy is `11`, you cannot start this task. However, if your current energy is `13`, you can complete this task, and your energy will be `3` after finishing it.

You can finish the tasks in **any order** you like.

Return _the **minimum** initial amount of energy you will need_ _to finish all the tasks_.

**Example 1:**

**Input:** tasks = [[1,2],[2,4],[4,8]]
**Output:** 8
**Explanation:**
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
**Explanation:**
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
**Explanation:**
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`

# Approaches
## Brute Force by Trying All Permutations
This approach explores every possible order of tasks. Since we can finish tasks in any order, we can generate all permutations of the tasks. For each permutation, we calculate the minimum initial energy required to complete the tasks in that specific order. The overall minimum energy will be the minimum among all calculated energies for all permutations.
**Time:** O(N! * N). There are N! possible permutations of the tasks. For each permutation, we iterate through N tasks to calculate the required energy. · **Space:** O(N), where N is the number of tasks. This space is used for the recursion stack and to store the list of tasks.
**Pros:** Guaranteed to find the optimal solution by checking every possibility.; Conceptually straightforward to understand.
**Cons:** Extremely inefficient due to its factorial time complexity.; Only feasible for very small input sizes (e.g., N ≤ 10).
### Explanation
The core idea is to exhaustively check every single sequence of tasks. We can implement this using a recursive function, say `permute(tasks, start)`, which generates all permutations of the tasks. When a full permutation is formed (i.e., `start` reaches the end of the list), we calculate the energy needed for this specific sequence. The energy calculation involves iterating through the permuted tasks, keeping a running sum of the `actual` costs, and finding the peak energy requirement. This peak is the maximum of `minimum_i + energy_spent_so_far` over all tasks `i` in the sequence. We maintain a global minimum variable, updating it whenever a permutation requires less initial energy than the minimum found so far.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    long minEnergy = Long.MAX_VALUE;

    public int minimumEffort(int[][] tasks) {
        List<int[]> taskList = new ArrayList<>();
        for (int[] task : tasks) {
            taskList.add(task);
        }
        permute(taskList, 0);
        return (int) minEnergy;
    }

    private void permute(List<int[]> tasks, int start) {
        if (start == tasks.size()) {
            calculateEnergyForPermutation(tasks);
            return;
        }
        for (int i = start; i < tasks.size(); i++) {
            Collections.swap(tasks, start, i);
            permute(tasks, start + 1);
            Collections.swap(tasks, start, i); // backtrack
        }
    }

    private void calculateEnergyForPermutation(List<int[]> permutation) {
        long requiredEnergy = 0;
        long energySpentSoFar = 0;
        for (int[] task : permutation) {
            int actual = task[0];
            int minimum = task[1];
            requiredEnergy = Math.max(requiredEnergy, minimum + energySpentSoFar);
            energySpentSoFar += actual;
        }
        minEnergy = Math.min(minEnergy, requiredEnergy);
    }
}
```
### Algorithm
- Use a recursive function to generate all permutations of the tasks.
- For each permutation, calculate the minimum initial energy required to complete the tasks in that specific order.
- The energy for a permutation `p_1, p_2, ..., p_n` is given by the formula: `max(m_{p_1}, m_{p_2} + a_{p_1}, ..., m_{p_n} + sum_{j=1}^{n-1} a_{p_j})`.
- Keep a global variable to track the minimum energy found across all permutations.
- The base case for the recursion is when a full permutation is generated. At this point, calculate its required energy and update the global minimum.
- Backtrack after each recursive call to explore other permutations.

## Dynamic Programming with Bitmasking
A more optimized approach than brute force is to use dynamic programming with a bitmask. We can define a state based on the subset of tasks that have been completed. A bitmask is a natural way to represent a subset of tasks, where each bit corresponds to a task. This avoids recomputing results for the same subset of tasks, which is a major drawback of the brute-force approach.
**Time:** O(N * 2^N). There are `2^N` states (masks), and for each state, we iterate through `N` tasks to compute the transition. · **Space:** O(2^N) to store the DP table and the precomputed sums of actual costs.
**Pros:** Significantly more efficient than the brute-force approach.; Finds the optimal solution by systematically building up from smaller subproblems.
**Cons:** The exponential time and space complexity makes it infeasible for the given constraints (N up to 10^5).; Practical only for small N (e.g., N ≤ 20).
### Explanation
Let `dp[mask]` be the minimum initial energy required to complete the set of tasks represented by `mask`. The state transition involves adding a new task to a smaller, already-solved subset. To compute `dp[mask]`, we can iterate through each task `i` belonging to the set `mask` and hypothesize that it was the last one to be completed. The subproblem is then to complete the tasks in `mask` excluding `i`, which is represented by `prev_mask = mask ^ (1 << i)`. The minimum energy for this subproblem is `dp[prev_mask]`. 

To perform task `i` after completing the tasks in `prev_mask`, our initial energy must be large enough. The energy spent on the previous tasks is `sum_actual[prev_mask]`. The energy required right before starting task `i` is `tasks[i][1]`. Thus, the initial energy must be at least `tasks[i][1] + sum_actual[prev_mask]`. Combining this with the energy needed for the subproblem, `dp[prev_mask]`, the total required energy for this specific sequence is `max(dp[prev_mask], tasks[i][1] + sum_actual[prev_mask])`. We take the minimum over all possible choices for the last task `i`.

```java
import java.util.Arrays;

class Solution {
    public int minimumEffort(int[][] tasks) {
        int n = tasks.length;
        if (n == 0) return 0;

        int[] dp = new int[1 << n];
        int[] sumActual = new int[1 << n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        // Pre-calculate sum of actual costs for each subset
        for (int mask = 1; mask < (1 << n); mask++) {
            int lsbIndex = Integer.numberOfTrailingZeros(mask);
            int prevMask = mask ^ (1 << lsbIndex);
            sumActual[mask] = sumActual[prevMask] + tasks[lsbIndex][0];
        }

        for (int mask = 1; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) { // If task i is in the current subset
                    int prevMask = mask ^ (1 << i);
                    int prevEnergy = dp[prevMask];
                    int neededForThis = tasks[i][1] + sumActual[prevMask];
                    int candidateEnergy = Math.max(prevEnergy, neededForThis);
                    dp[mask] = Math.min(dp[mask], candidateEnergy);
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}
```
### Algorithm
- Define a DP state `dp[mask]` as the minimum initial energy to complete the subset of tasks represented by `mask`.
- A bitmask is used where the `i`-th bit is 1 if task `i` is in the subset.
- Initialize `dp` array of size `2^N` with a large value, and set `dp[0] = 0`.
- To compute `dp[mask]`, we iterate through each task `i` in the subset `mask` and consider it as the last task performed.
- The previous state is `prev_mask = mask ^ (1 << i)`.
- The energy required for this sequence is `max(dp[prev_mask], m_i + sum_actual[prev_mask])`, where `sum_actual[prev_mask]` is the sum of `actual` costs for tasks in `prev_mask`.
- The transition is `dp[mask] = min(dp[mask], max(dp[prev_mask], m_i + sum_actual[prev_mask]))`.
- The final answer is `dp[(1<<N) - 1]`.

## Greedy Approach with Sorting
The most efficient solution is a greedy approach. The key insight is to determine the optimal order to perform the tasks. By analyzing how the energy requirement changes when we swap two adjacent tasks, we can deduce a sorting criterion. It turns out that it's always optimal to perform tasks with a larger difference between their `minimum` and `actual` energy costs first. This is because these tasks have the tightest constraints; they require a large energy reserve (`minimum`) relative to what they consume (`actual`), so getting them out of the way early, when our available energy is highest, is beneficial.
**Time:** O(N log N), which is dominated by the sorting step. The subsequent loop to calculate the energy runs in O(N). · **Space:** O(log N) or O(N), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for objects is based on Timsort, which may use O(N) space in the worst case.
**Pros:** Highly efficient with a time complexity dominated by sorting.; Simple to implement once the greedy criterion is established.; Handles large constraints effectively.
**Cons:** The correctness of the greedy strategy is not immediately obvious and relies on a proof (e.g., an exchange argument).
### Explanation
Let's prove the greedy strategy with an exchange argument. Consider any two adjacent tasks in a sequence, `T_i = [a_i, m_i]` and `T_j = [a_j, m_j]`. Let the energy required before starting this pair be `E`. If we do `T_i` then `T_j`, the energy needed is `max(m_i, m_j + a_i)`. If we do `T_j` then `T_i`, it's `max(m_j, m_i + a_j)`. We want to perform the task that results in a smaller energy requirement first. It can be shown that if `m_i - a_i > m_j - a_j`, then `max(m_i, m_j + a_i) <= max(m_j, m_i + a_j)`. This implies that placing the task with the higher `minimum - actual` difference first is always optimal.

So, the algorithm is to first sort the tasks in descending order of `minimum - actual`. Then, we can calculate the required initial energy in a single pass. Let the sorted tasks be `p_1, ..., p_n`. The initial energy `E` must satisfy `E - sum_{k=1}^{i-1} a_{p_k} >= m_{p_i}` for all `i`. This is equivalent to `E >= m_{p_i} + sum_{k=1}^{i-1} a_{p_k}`. The minimum `E` is therefore the maximum of these values over all `i`.

```java
import java.util.Arrays;

class Solution {
    public int minimumEffort(int[][] tasks) {
        // Sort tasks by the difference (minimum - actual) in descending order.
        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));

        long energyNeeded = 0;
        long actualSum = 0;

        for (int[] task : tasks) {
            int actual = task[0];
            int minimum = task[1];
            
            // The energy required must be enough to cover the minimum for this task
            // on top of the energy already spent on previous tasks.
            energyNeeded = Math.max(energyNeeded, actualSum + minimum);
            
            // Accumulate the actual cost for the next iteration.
            actualSum += actual;
        }

        return (int) energyNeeded;
    }
}
```
### Algorithm
- The core idea is to find the optimal order for performing tasks. This can be found using a greedy strategy.
- The greedy criterion is to sort the tasks in descending order based on the difference `minimum - actual`.
- After sorting, iterate through the tasks to calculate the total initial energy needed.
- Initialize `energyNeeded = 0` and `actualSum = 0`.
- For each task `[actual, minimum]` in the sorted list:
  - The peak energy required at this step is `actualSum + minimum` (the sum of costs of tasks already done, plus the minimum requirement for the current task).
  - Update the overall `energyNeeded = max(energyNeeded, actualSum + minimum)`.
  - Add the current task's `actual` cost to the running sum: `actualSum += actual`.
- Return `energyNeeded`.

# Solutions
### Java

```java
class Solution {
public
  int minimumEffort(int[][] tasks) {
    Arrays.sort(tasks, (a, b)->a[0] - b[0] - (a[1] - b[1]));
    int ans = 0, cur = 0;
    for (var task : tasks) {
      int a = task[0], m = task[1];
      if (cur < m) {
        ans += m - cur;
        cur = m;
      }
      cur -= a;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumEffort(vector<vector<int>> &tasks) {
    sort(tasks.begin(), tasks.end(), [&](const auto &a, const auto &b) {
      return a[0] - a[1] < b[0] - b[1];
    });
    int ans = 0, cur = 0;
    for (auto &task : tasks) {
      int a = task[0], m = task[1];
      if (cur < m) {
        ans += m - cur;
        cur = m;
      }
      cur -= a;
    }
    return ans;
  }
};

```

### Python

```python
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

```