Minimum Initial Energy to Finish Tasks

hard greedy sorting array

Problem

Each task is [actual, minimum]: actual energy is spent to finish it, but you need at least minimum energy on hand to begin it (with actual ≤ minimum). You may finish tasks in any order. Return the minimum initial energy needed to complete every task.

Inputtasks = [[1,2],[2,4],[4,8]]

Output8

Start with 8. Do [4,8] (need 8, have 8 → 4 left), then [2,4] (→ 2), then [1,2] (→ 1). Starting with 7 fails: you could never begin [4,8].

tasks (actual:minimum, comma-separated)

def minimumEffort(tasks):
    # Do tasks with the smallest slack (minimum - actual) first;
    # the big "reservation gap" tasks are best saved for last.
    tasks.sort(key=lambda t: t[1] - t[0])
    energy = 0                      # min energy needed so far
    for actual, minimum in tasks:
        # After this task we must still hold `energy`, so before it
        # we need energy + actual; we must also clear the `minimum` bar.
        energy = max(energy + actual, minimum)
    return energy

function minimumEffort(tasks) {
  // Do tasks with the smallest slack (minimum - actual) first;
  // the big "reservation gap" tasks are best saved for last.
  tasks.sort((a, b) => (a[1] - a[0]) - (b[1] - b[0]));
  let energy = 0;                  // min energy needed so far
  for (const [actual, minimum] of tasks) {
    // After this task we must still hold `energy`, so before it
    // we need energy + actual; we must also clear the `minimum` bar.
    energy = Math.max(energy + actual, minimum);
  }
  return energy;
}

int minimumEffort(int[][] tasks) {
    // Do tasks with the smallest slack (minimum - actual) first;
    // the big "reservation gap" tasks are best saved for last.
    Arrays.sort(tasks, (a, b) -> (a[1] - a[0]) - (b[1] - b[0]));
    int energy = 0;                 // min energy needed so far
    for (int[] t : tasks) {
        // Before the task we need energy + actual to keep the
        // reserve, and must also clear the `minimum` bar.
        energy = Math.max(energy + t[0], t[1]);
    }
    return energy;
}

int minimumEffort(vector<vector<int>>& tasks) {
    // Do tasks with the smallest slack (minimum - actual) first;
    // the big "reservation gap" tasks are best saved for last.
    sort(tasks.begin(), tasks.end(), [](auto& a, auto& b) {
        return (a[1] - a[0]) < (b[1] - b[0]);
    });
    int energy = 0;                 // min energy needed so far
    for (auto& t : tasks) {
        // Before the task we need energy + actual to keep the
        // reserve, and must also clear the `minimum` bar.
        energy = max(energy + t[0], t[1]);
    }
    return energy;
}

Explanation

Each task spends actual energy but demands a higher minimum just to begin. The gap slack = minimum − actual is the energy that must be present but is not consumed — a reservation that frees up the moment the task finishes.

Think backwards. Suppose we already fixed the order. Walk from the last task to the first, tracking energy = the energy we must have entering the current suffix. For a task [actual, minimum], after finishing it we still need energy for the rest, so entering it we need energy + actual. But we also cannot even start unless we hold minimum. Hence energy = max(energy + actual, minimum).

Which order minimizes the final answer? The greedy claim: do tasks with the smallest slack first and the largest slack last. Intuitively, a task with a huge reservation gap should sit at the end, when little energy remains, so its tall minimum bar is checked against the smallest running total. Save the “cheap to run but scary to start” tasks for when your reserve is already low.

An exchange argument confirms it: for two adjacent tasks, swapping them to put the smaller-slack one first never increases the required energy. So we sort by minimum − actual ascending and fold the recurrence over the array in one pass.

Example [[1,2],[2,4],[4,8]] — slacks are 1, 2, 4, already sorted. Folding: max(0+1,2)=2, then max(2+2,4)=4, then max(4+4,8)=8. The answer is 8.

Time: O(n log n) Space: O(1) extra (in-place sort)