Minimum Initial Energy to Finish Tasks
HardPrompt
You are given an array tasks where tasks[i] = [actuali, minimumi]:
actualiis the actual amount of energy you spend to finish theithtask.minimumiis the minimum amount of energy you require to begin theithtask.
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 <= 1051 <= actuali <= minimumi <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
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.
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_nis 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.
Walkthrough
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.
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); }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- Define a DP state
dp[mask]as the minimum initial energy to complete the subset of tasks represented bymask. - A bitmask is used where the
i-th bit is 1 if taskiis in the subset. - Initialize
dparray of size2^Nwith a large value, and setdp[0] = 0. - To compute
dp[mask], we iterate through each taskiin the subsetmaskand 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]), wheresum_actual[prev_mask]is the sum ofactualcosts for tasks inprev_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].
Walkthrough
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.
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]; }}Complexity
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.
Trade-offs
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).
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.
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 = 0andactualSum = 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
actualcost to the running sum:actualSum += actual.
- The peak energy required at this step is
- Return
energyNeeded.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.