Minimum Initial Energy to Finish Tasks solution and explanation
Google
9 more videos on this problem
Minimum Initial Energy to Finish Tasks | Simplified | Intuition | Leetcode 1665 | codestorywithMIKcodestorywithMIK · 25:43 · 8K views
Minimum Initial Energy to Finish Tasks | Leetcode 1665 | leetcode solutionEasyLeetcode · 12:19 · 2K views
LeetCode 1665. Minimum Initial Energy to Finish TasksHappy Coding · 15:30 · 1K views
LeetCode 1665. Minimum Initial Energy to Finish Tasks | Visualization | PythonAH Tech · 6:28 · 721 views
1665. Minimum Initial Energy to Finish Tasks (Leetcode Hard)Programming Live with Larry · 10:51 · 665 views
1665. Minimum Initial Energy to Finish Tasks | Leetcode Daily - PythonLeetcode Daily · 7:05 · 488 views
Daily Leetcode #2233: May 12, 2026 - 1665. Minimum Initial Energy to Finish TasksProgramming Live with Larry · 30:58 · 447 views
Minimum Initial Energy to Finish Tasks | LeetCode 1665 - Pythonimpoldev · 7:57 · 295 views
Minimum Initial Energy to Finish Tasks | Leetcode 1665 | Greedy | Sorting | Intuitive | SimplifiedPragya Gupta · 19:58 · 257 views
Minimum Initial Energy to Finish Tasks | LeetCode 1665 | Greedy | Java Code | Developer CoderDeveloper Coder · 13:23 · 248 views
The problem
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
Approach overview
Problem 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.
Approach 1: Sorting by Energy Surplus
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.
def minimumEnergy(tasks):
tasks.sort(key=lambda x: x[1] - x[0], reverse=True)
currentEnergy = 0
totalEnergy = 0
for actual, minimum in tasks:
totalEnergy = max(totalEnergy, currentEnergy + minimum)
currentEnergy += actual
return totalEnergy
print(minimumEnergy([[1, 2], [2, 4], [4, 8]]))import java.util.Arrays;
public class MinimumEnergy {
public static int minimumEnergy(int[][] tasks) {
Arrays.sort(tasks, (a, b) -> Integer.compare(b[1] - b[0], a[1] - a[0]));
int currentEnergy = 0, totalEnergy = 0;
for (int[] task : tasks) {
totalEnergy = Math.max(totalEnergy, currentEnergy + task[1]);
currentEnergy += task[0];
}
return totalEnergy;
}
public static void main(String[] args) {
int[][] tasks = {{1, 2}, {2, 4}, {4, 8}};
System.out.println(minimumEnergy(tasks));
}
}#include <vector>
#include <algorithm>
using namespace std;
int minimumEnergy(vector<vector<int>>& tasks) {
sort(tasks.begin(), tasks.end(), [](const vector<int>& a, const vector<int>& b) {
return (b[1] - b[0]) < (a[1] - a[0]);
});
int currentEnergy = 0, totalEnergy = 0;
for (auto& task : tasks) {
totalEnergy = max(totalEnergy, currentEnergy + task[1]);
currentEnergy += task[0];
}
return totalEnergy;
}
int main() {
vector<vector<int>> tasks = {{1, 2}, {2, 4}, {4, 8}};
cout << minimumEnergy(tasks) << endl;
return 0;
}function minimumEnergy(tasks) {
tasks.sort((a, b) => (b[1] - b[0]) - (a[1] - a[0]));
let currentEnergy = 0;
let totalEnergy = 0;
for (let [actual, minimum] of tasks) {
totalEnergy = Math.max(totalEnergy, currentEnergy + minimum);
currentEnergy += actual;
}
return totalEnergy;
}
console.log(minimumEnergy([[1, 2], [2, 4], [4, 8]]));#include <stdio.h>
#include <stdlib.h>
int cmp(const void* a, const void* b) {
int* taskA = *(int**)a;
int* taskB = *(int**)b;
return (taskB[1] - taskB[0]) - (taskA[1] - taskA[0]);
}
int minimumEnergy(int** tasks, int tasksSize, int* tasksColSize) {
qsort(tasks, tasksSize, sizeof(int*), cmp);
int currentEnergy = 0, totalEnergy = 0;
for(int i = 0; i < tasksSize; i++) {
totalEnergy = totalEnergy > tasks[i][1] ? totalEnergy : tasks[i][1];
currentEnergy += tasks[i][0];
}
return totalEnergy;
}
int main() {
int tasksArray[][2] = {{1, 2}, {2, 4}, {4, 8}};
int* tasks[] = {tasksArray[0], tasksArray[1], tasksArray[2]};
int tasksColSize[] = {2, 2, 2};
printf("%d
", minimumEnergy(tasks, 3, tasksColSize));
return 0;
}using System;
using System.Linq;
public class MinimumEnergy {
public static int MinimumEnergy(int[][] tasks) {
Array.Sort(tasks, (a, b) => (b[1] - b[0]).CompareTo(a[1] - a[0]));
int currentEnergy = 0, totalEnergy = 0;
foreach (var task in tasks) {
totalEnergy = Math.Max(totalEnergy, currentEnergy + task[1]);
currentEnergy += task[0];
}
return totalEnergy;
}
public static void Main() {
int[][] tasks = new int[][] { new int[] { 1, 2 }, new int[] { 2, 4 }, new int[] { 4, 8 } };
Console.WriteLine(MinimumEnergy(tasks));
}
}This Python solution sorts the tasks based on their energy surplus in descending order. By iterating through the sorted tasks, the total initial energy is derived by ensuring enough energy is reserved at the start to cover the most costly tasks.
The overall time complexity is O(N log N) due to sorting of tasks, and the space complexity is O(1) additional.
Approach 2: Binary Search for Minimum Energy
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.
def can_complete(energy, tasks):
for actual, minimum in tasks:
if energy < minimum:
return False
energy -= actual
return True
def minimum_energy(tasks):
total = sum(task[0] for task in tasks)
max_min = max(task[1] for task in tasks)
left, right = max_min, total
while left < right:
mid = (left + right) // 2
if can_complete(mid, tasks):
right = mid
else:
left = mid + 1
return left
print(minimum_energy([[1, 2], [2, 4], [4, 8]]))public class MinimumEnergyBinarySearch {
public static boolean canComplete(int energy, int[][] tasks) {
for (int[] task : tasks) {
if (energy < task[1]) return false;
energy -= task[0];
}
return true;
}
public static int minimumEnergy(int[][] tasks) {
int total = 0, maxMin = 0;
for (int[] task : tasks) {
total += task[0];
maxMin = Math.max(maxMin, task[1]);
}
int left = maxMin, right = total;
while (left < right) {
int mid = left + (right - left) / 2;
if (canComplete(mid, tasks)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void main(String[] args) {
int[][] tasks = {{1, 2}, {2, 4}, {4, 8}};
System.out.println(minimumEnergy(tasks));
}
}#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool canComplete(int energy, const vector<vector<int>>& tasks) {
for (const auto& task : tasks) {
if (energy < task[1]) return false;
energy -= task[0];
}
return true;
}
int minimumEnergy(vector<vector<int>>& tasks) {
int total = 0, maxMin = 0;
for (const auto& task : tasks) {
total += task[0];
maxMin = max(maxMin, task[1]);
}
int left = maxMin, right = total;
while (left < right) {
int mid = left + (right - left) / 2;
if (canComplete(mid, tasks)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int main() {
vector<vector<int>> tasks = {{1, 2}, {2, 4}, {4, 8}};
cout << minimumEnergy(tasks) << endl;
return 0;
}function canComplete(energy, tasks) {
for (const [actual, minimum] of tasks) {
if (energy < minimum) return false;
energy -= actual;
}
return true;
}
function minimumEnergy(tasks) {
let total = tasks.reduce((sum, task) => sum + task[0], 0);
let maxMin = Math.max(...tasks.map(task => task[1]));
let left = maxMin, right = total;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (canComplete(mid, tasks)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
console.log(minimumEnergy([[1, 2], [2, 4], [4, 8]]));#include <stdio.h>
#include <stdbool.h>
bool canComplete(int energy, int** tasks, int tasksSize) {
for (int i = 0; i < tasksSize; i++) {
if (energy < tasks[i][1]) return false;
energy -= tasks[i][0];
}
return true;
}
int minimumEnergy(int** tasks, int tasksSize, int tasksColSize) {
int total = 0, maxMin = 0;
for (int i = 0; i < tasksSize; i++) {
total += tasks[i][0];
if (tasks[i][1] > maxMin) maxMin = tasks[i][1];
}
int left = maxMin, right = total;
while (left < right) {
int mid = left + (right - left) / 2;
if (canComplete(mid, tasks, tasksSize)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int main() {
int tasksArray[][2] = {{1, 2}, {2, 4}, {4, 8}};
int* tasks[] = {tasksArray[0], tasksArray[1], tasksArray[2]};
int tasksColSize = 2;
printf("%d
", minimumEnergy(tasks, 3, tasksColSize));
return 0;
}using System;
public class MinimumEnergyBinarySearch {
public static bool CanComplete(int energy, int[][] tasks) {
foreach (var task in tasks) {
if (energy < task[1]) return false;
energy -= task[0];
}
return true;
}
public static int MinimumEnergy(int[][] tasks) {
int total = 0, maxMin = 0;
foreach (var task in tasks) {
total += task[0];
maxMin = Math.Max(maxMin, task[1]);
}
int left = maxMin, right = total;
while (left < right) {
int mid = left + (right - left) / 2;
if (CanComplete(mid, tasks)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void Main() {
int[][] tasks = { new int[] { 1, 2 }, new int[] { 2, 4 }, new int[] { 4, 8 } };
Console.WriteLine(MinimumEnergy(tasks));
}
}This Python solution utilizes binary search to explore potential starting energy levels. Simulated task iterations at each binary search step ensure the task can be completed, allowing search range refinement toward an optimal initial energy value.
Time complexity is O(N log S) given sort operations, and space complexity is O(1) as operations are in-place.
Approach 3: Greedy + Custom Sorting
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)$.
function minimumEffort(tasks: number[][]): number {
tasks.sort((a, b) => a[0] - a[1] - (b[0] - b[1]));
let ans = 0;
let cur = 0;
for (const [a, m] of tasks) {
if (cur < m) {
ans += m - cur;
cur = m;
}
cur -= a;
}
return ans;
}func minimumEffort(tasks [][]int) (ans int) {
sort.Slice(tasks, func(i, j int) bool { return tasks[i][0]-tasks[i][1] < tasks[j][0]-tasks[j][1] })
cur := 0
for _, task := range tasks {
a, m := task[0], task[1]
if cur < m {
ans += m - cur
cur = m
}
cur -= a
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting by Energy Surplus | The overall time complexity is |
| Binary Search for Minimum Energy | Time complexity is |
| Greedy + Custom Sorting | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Initial Energy to Finish Tasks easy or hard?
LeetCode classifies this problem as Hard because the correct greedy ordering is not immediately obvious. Many first attempts try brute-force permutations or dynamic programming, which are inefficient. Recognizing the sorting rule based on the energy surplus difference is the key insight.
Minimum Initial Energy to Finish Tasks Python/Java solution
In Python or Java, store tasks as pairs and sort them by (minimumRequired - actualCost) in descending order. Iterate through the sorted list while tracking current energy and increasing the initial energy whenever the requirement exceeds the current level. This greedy approach runs in O(n log n) time and works efficiently for large inputs.
How to solve Minimum Initial Energy to Finish Tasks in O(n)?
A strictly O(n) solution is not practical because the correct task order depends on comparing the difference between required and actual energy for all tasks. Sorting by this value is necessary to guarantee the optimal order, which introduces an O(n log n) step. After sorting, the energy calculation itself runs in O(n).
What is the best approach for Minimum Initial Energy to Finish Tasks?
The optimal approach is a greedy strategy that sorts tasks by the difference between minimum required energy and actual energy cost (minimumRequired - actualCost). Tasks with the largest gap are executed first because they impose stricter starting conditions. After sorting, iterate once and adjust the initial energy whenever the current energy is below the task's requirement. The overall complexity is O(n log n) due to sorting.
Is Minimum Initial Energy to Finish Tasks asked at Google/Amazon/Meta?
This type of greedy scheduling problem frequently appears in interviews at companies like Google, Amazon, and Meta. Variations test your ability to reorder tasks based on constraints and identify the correct greedy criterion. Interviewers often expect candidates to justify why sorting by (minimumRequired - actualCost) leads to the optimal solution.
What data structure is used in Minimum Initial Energy to Finish Tasks?
The core structure is an array of task pairs containing actual energy cost and minimum required energy. The algorithm relies on sorting this array based on a computed key and then iterating through it once while maintaining a running energy value. No advanced structures beyond arrays and a sorting routine are required.
What is the time complexity of Minimum Initial Energy to Finish Tasks?
The optimal greedy solution runs in O(n log n) time because tasks must be sorted based on their energy surplus difference. After sorting, a single linear pass computes the minimum starting energy, which takes O(n). Space complexity is O(1) aside from the input array if sorting is done in place.