Minimum Initial Energy to Finish Tasks

Hard
1463.

Minimum Initial Energy to Finish Tasks

Minimum Initial Energy to Finish Tasks is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

You have a list of tasks, where tasks[i] = [actual_i, minimum_i]:

  • actual_i is the energy the task consumes when you do it.
  • minimum_i is 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^5
  • 1 <= actual_i <= minimum_i <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} tasks
 * @return {number}
 */
var minimumEffort = function(tasks) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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_i is the energy the task consumes when you do it.
  • minimum_i is 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^5
  • 1 <= actual_i <= minimum_i <= 10^4

Hints for Minimum Initial Energy to Finish Tasks

  1. Hint 1

    The total energy spent is fixed; what varies is how much slack you need before each task.

  2. Hint 2

    A task with a large gap minimum - actual is best done early, while you still have plenty of energy.

  3. Hint 3

    Sort by minimum - actual ascending 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

  1. Sort the tasks by minimum - actual ascending.
  2. Start with need = 0 — the energy required after the last task.
  3. For each task in that order (the last task to be done first): need = max(need + actual, minimum).
  4. 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 minimum alone is wrong — the deciding quantity is the gap minimum - 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 need

Java

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