1665. Minimum Initial Energy to Finish Tasks

Intuition

Each task has two values:

• actual: energy consumed
• minimum: energy required before starting

The risky tasks are those with large unused requirement, meaning minimum - actual is large. These tasks need a high energy level to start but do not consume as much as they require. Doing them earlier preserves feasibility for the rest.

So sort tasks by descending minimum - actual.

Greedy Reasoning

Consider two tasks A and B.

If we do A before B, the required initial energy must cover:

max(A.minimum, A.actual + B.minimum)

If we do B before A, it must cover:

max(B.minimum, B.actual + A.minimum)

Doing A first is no worse when:

A.minimum - A.actual >= B.minimum - B.actual

Therefore tasks should be ordered by descending minimum - actual.

Approach

1. Sort tasks by descending minimum - actual.
2. Track:
   • initial: total initial energy added so far
   • current: current available energy during simulation
3. For each task:
   • if current < minimum, add the difference to both initial and current
   • complete the task by subtracting actual from current
4. Return initial.

Complexity

• Time: O(n log n), sorting dominates
• Space: O(1) extra, ignoring sorting implementation details

Edge Cases

• One task -> answer is its minimum
• Tasks where actual == minimum
• Large number of tasks -> sorting is required, simulation is linear

from typing import List


class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        """
        1665. Minimum Initial Energy to Finish Tasks
        Time: O(n log n)
        Space: O(1)
        """
        tasks.sort(key=lambda task: task[1] - task[0], reverse=True)

        initial = 0
        current = 0

        for actual, minimum in tasks:
            if current < minimum:
                needed = minimum - current
                initial += needed
                current += needed

            current -= actual

        return initial

import java.util.Arrays;

/**
 * 1665. Minimum Initial Energy to Finish Tasks
 * Time: O(n log n)
 * Space: O(1)
 */
class Solution {
    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));

        int initial = 0;
        int current = 0;

        for (int[] task : tasks) {
            int actual = task[0];
            int minimum = task[1];

            if (current < minimum) {
                int needed = minimum - current;
                initial += needed;
                current += needed;
            }

            current -= actual;
        }

        return initial;
    }
}