356. Minimum Initial Energy to Finish Tasks

Sort tasks by the gap (minimum - actual) in descending order. Tasks with larger gaps waste more energy on the threshold requirement, so doing them first when energy is highest minimizes the total starting energy needed.

Approach

Greedy: sort tasks so that the ones requiring the most "wasted" energy (the gap between the threshold and the actual cost) come first.

1. For each task [actual, minimum], compute the gap = minimum - actual. This is the energy you need just to qualify but don't spend.
2. Sort tasks by gap in descending order (largest gap first).
3. Simulate: walk through the sorted tasks, tracking energy (total initial energy needed) and cur (current energy level).
   • If cur < minimum for the current task, top up: energy += minimum - cur, then set cur = minimum.
   • Spend the task: cur -= actual.
4. Return energy.

Walk-through

Input: tasks = [[1,2],[2,4],[4,8]]

Gaps: [1, 2, 4] → sorted descending: [[4,8],[2,4],[1,2]]

Answer: 8

Why it works

Every task forces you to have at least minimum energy, but only consumes actual. The leftover (minimum - actual) is wasted overhead. By doing high-gap tasks first — when your energy is at its peak — you satisfy their thresholds without needing extra top-ups. Low-gap tasks later naturally fit under whatever energy remains.

Edge cases

• Single task [[5,5]]: gap is 0, you need exactly 5.
• All gaps equal: any order works, total energy = max minimum among tasks.

import java.util.*;

class Solution {
    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> Integer.compare(b[1] - b[0], a[1] - a[0]));
        int energy = 0, cur = 0;
        for (int[] task : tasks) {
            int actual = task[0], minimum = task[1];
            if (cur < minimum) {
                energy += minimum - cur;
                cur = minimum;
            }
            cur -= actual;
        }
        return energy;
    }
}