Minimum Initial Energy to Finish Tasks
Hard · Greedy · Array · Greedy · Sorting
Problem
You are given an array tasks where tasks[i] = [actual_i, minimum_i]:
- actual_i is the energy you spend when you complete task i;
- minimum_i is the energy you must have before starting task i.
With task [4, 6] and energy 5 you cannot start it; with energy 7 you can, and finish with 3. You may do the tasks in any order, each exactly once.
Return the smallest initial energy that lets you finish every task.
Examples
Input: tasks = [[2,3],[3,7],[1,5]] Output: 8
With 8: do [3,7] (8 to 5), then [1,5] (5 to 4), then [2,3] (4 to 2). 7 is not enough for any order.
Input: tasks = [[5,5]] Output: 5
The single task needs 5 on hand and uses all of it.
Input: tasks = [[1,10],[1,2]] Output: 10
Start [1,10] with 10, leaving 9, more than the 2 the other task needs.
Constraints
- 1 <= tasks.length <= 10^5
- 1 <= actual_i <= minimum_i <= 10^4
Approaches
- Baseline: best order over every subset — time O(2^n · n), space O(2^n)
Follow-up
When the order is fixed, the same backward formula gives the answer with no sorting at all; when a starting energy is given, sorting and one forward pass tell you whether it is enough. The use cases ask both.
Related problems
Start free on Cariara · Coding problems · System design studio
