Minimum Initial Energy to Finish Tasks — Problem & Solution
Minimum Initial Energy to Finish Tasks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Initial Energy to Finish Tasks is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have a list of tasks, where tasks[i] = [actual_i, minimum_i]:
actual_iis the energy the task consumes when you do it.minimum_iis the energy you must have before you may start it.
For example, with [10, 12] and 11 energy you cannot start; with 13 energy you can, and you finish with 3.
You may do the tasks in any order. Return the minimum initial energy that lets you finish all of them.
Example 1
Input: tasks = [[2,5],[3,4]]
Output: 6
Explanation: Start with 6: do `[2,5]` (left with 4), then `[3,4]` (left with 1).
Example 2
Input: tasks = [[1,2],[2,4],[4,8]]
Output: 8
Example 3
Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
Output: 32
Constraints
1 <= tasks.length <= 10^51 <= actual_i <= minimum_i <= 10^4
Hints for Minimum Initial Energy to Finish Tasks
Hint 1
The total energy spent is fixed; what varies is how much slack you need before each task.
Hint 2
A task with a large gap
minimum - actualis best done early, while you still have plenty of energy.Hint 3
Sort by
minimum - actualascending and build the answer backwards:energy = max(energy + actual, minimum)for each task.
How to solve Minimum Initial Energy to Finish Tasks
Do tasks in decreasing order of minimum - actual. Computing the needed energy is easiest backwards: process tasks from the last one done (smallest gap) to the first, keeping the energy needed from that point on.
Approach
- Sort the tasks by
minimum - actualascending. - Start with
need = 0— the energy required after the last task. - For each task in that order (the last task to be done first):
need = max(need + actual, minimum). - Return
need.
Why it works
Exchange argument: take two adjacent tasks a then b with min_a - act_a < min_b - act_b. Swapping them to b then a never increases the energy required, because the binding constraint act_b + min_a (doing a second) exceeds act_a + min_b. So the order by decreasing gap is optimal, and walking it backwards computes the least starting energy exactly: before a task you need both its minimum and enough to cover it plus everything after.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting by
minimumalone is wrong — the deciding quantity is the gapminimum - actual. - The backwards pass processes the smallest gap first because that task is done last.
- The answer can reach 10^9; it still fits in 32 bits, but 64-bit accumulation is the safe habit.
Reference solution
Python
from typing import List
def minimumEffort(tasks: List[List[int]]) -> int:
need = 0
for actual, minimum in sorted(tasks, key=lambda t: t[1] - t[0]):
need = max(need + actual, minimum)
return needJava
public static int minimumEffort(int[][] tasks) {
int[][] t = tasks.clone();
Arrays.sort(t, (a, b) -> Integer.compare(a[1] - a[0], b[1] - b[0]));
long need = 0;
for (int[] task : t) need = Math.max(need + task[0], task[1]);
return (int) need;
}C++
int minimumEffort(vector<vector<int>>& tasks) {
vector<vector<int>> t(tasks);
sort(t.begin(), t.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] - a[0] < b[1] - b[0];
});
long long need = 0;
for (auto& task : t) need = max(need + task[0], (long long)task[1]);
return (int)need;
}JavaScript
var minimumEffort = function(tasks) {
var t = tasks.slice().sort(function(a, b) { return (a[1] - a[0]) - (b[1] - b[0]); });
var need = 0;
for (var i = 0; i < t.length; i++) need = Math.max(need + t[i][0], t[i][1]);
return need;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms