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 <= 1051 <= actuali <= minimumi <= 104Problem Overview: You are given tasks where each task has two values: the actual energy spent to complete it and the minimum energy required to start it. The goal is to determine the minimum initial energy needed so you can complete every task in some order without your energy dropping below the required threshold.
Approach 1: Binary Search for Minimum Energy (O(n log n) time, O(1) space)
This approach treats the answer as a search space. Assume a candidate starting energy and simulate whether all tasks can be completed. To maximize feasibility, sort tasks so those with the largest gap between minimumRequired and actualCost are handled first. For each candidate value, iterate through tasks, check if current energy satisfies the minimum requirement, and subtract the actual cost. Binary search narrows the smallest starting energy that passes the simulation. Sorting dominates the runtime, resulting in O(n log n) time with constant extra space.
Approach 2: Greedy Sorting by Energy Surplus (O(n log n) time, O(1) space)
The key insight: tasks with a larger difference between required energy and actual cost are more restrictive and should be executed earlier. Sort tasks by (minimumRequired - actualCost) in descending order. Then iterate through the sorted tasks while maintaining your current energy. If the current energy is less than the task's required minimum, increase the initial energy so the requirement is satisfied. After completing the task, subtract its actual cost. This greedy ordering ensures you never face a task later that requires more upfront energy than you can afford. The sort step takes O(n log n) time and the single pass simulation is O(n), with O(1) additional space.
Both strategies rely on ordering tasks by how restrictive they are. The greedy version computes the minimum energy directly and is simpler to implement than repeatedly validating candidates with binary search.
Recommended for interviews: The greedy sorting strategy is what most interviewers expect. Recognizing that tasks with the largest minimumRequired - actualCost gap must be handled first demonstrates strong intuition with greedy algorithms and sorting. The binary search method shows an alternative reasoning path but is usually considered less direct. Understanding both strengthens your problem-solving toolkit for array-based scheduling and ordering problems.
This approach involves determining the 'energy surplus' needed for a task, calculated as minimum[i] - actual[i]. To minimize the starting energy, we perform the tasks with the highest surplus first. This guarantees that we have enough energy when tackling the most demanding tasks.
The solution uses a custom comparator function to sort tasks based on the difference between minimum[i] and actual[i]. The tasks are then processed in this order, and we calculate the minimum starting energy needed to complete them without running out of energy at any point.
The time complexity is O(N log N) due to sorting, where N is the number of tasks. The space complexity is O(N) if considering the additional space used by the sorting algorithm.
In this approach, we leverage binary search to determine the minimum initial energy needed to complete all tasks. We define a range between the maximum minimal requirement and the sum of all actual energies, and perform a binary search on this range. For each midpoint, we simulate task completion to verify if starting with that energy suffices.
This implementation applies binary search over the possible range of initial energy values. For a given midpoint, it checks if all tasks can be completed starting with that energy, adjusting the search range accordingly based on results.
The algorithm has a time complexity of O(N log S), where N is the number of tasks and S is the combined sum of actual energies. Space complexity is O(1) additional.
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.,
$
E-sum_{i=1}^{n-1} a_i geq m_n
We can express m_n as a_n+(m_n - a_n), and then transform the above formula to get:
E-sum_{i=1}^{n-1} a_i geq a_n+(m_n - a_n)
Rearranging, we get:
E geq sum_{i=1}^{n} a_i + (m_n - a_n)
Where sum_{i=1}^{n} a_i is fixed. To minimize the initial energy level E, we need to minimize m_n - a_n, i.e., maximize a_n-m_n.
Therefore, we can sort the tasks in ascending order of a_i-m_i. Then we traverse the tasks from front to back. For each task, if the current energy level cur is less than m_i, we need to increase the energy level by m_i - cur to make the current energy level exactly equal to m_i. Then we complete the task and update cur = cur - a_i. Continue traversing until all tasks are completed, and we can get the minimum initial energy level required.
The time complexity is O(ntimes log n), where n is the number of tasks. Ignoring the space overhead of sorting, the space complexity is O(1)$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting by Energy Surplus | The time complexity is |
| Binary Search for Minimum Energy | The algorithm has a time complexity of |
| Greedy + Custom Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Sorting by Energy Surplus | O(n log n) | O(1) | Preferred solution for interviews. Directly computes minimum starting energy after sorting tasks by constraint severity. |
| Binary Search for Minimum Energy | O(n log n) | O(1) | Useful when framing the problem as checking feasibility of a starting energy value. |
Minimum Initial Energy to Finish Tasks | Leetcode 1665 | leetcode solution • EasyLeetcode • 1,893 views views
Watch 6 more video solutions →Practice Minimum Initial Energy to Finish Tasks with our built-in code editor and test cases.
Practice on FleetCode