LeetCode 1665 - Minimum Initial Energy to Finish Tasks

The problem gives us a list of tasks, where each task is represented as [actual, minimum]. For every task: - minimum is the amount of energy we must currently have before we are allowed to start the task.

leetcodehardarraygreedysorting

LeetCode Problem 1665

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem gives us a list of tasks, where each task is represented as [actual, minimum].

For every task:

  • minimum is the amount of energy we must currently have before we are allowed to start the task.
  • actual is the amount of energy that gets consumed after finishing the task.

Suppose a task is [4, 10]. We need at least 10 energy to begin it. After completing it, our energy decreases by 4.

The important detail is that tasks can be completed in any order. Our goal is to determine the smallest possible initial energy such that there exists some ordering of tasks that allows us to complete all of them.

This is fundamentally an ordering optimization problem. Different task orders require different starting energy levels. We want the order that minimizes the required initial energy.

The constraints are large:

  • Up to 10^5 tasks
  • Each value can be up to 10^4

Because of this, exponential or factorial solutions are impossible. We need something around O(n log n).

Another important observation is that every task satisfies:

actual <= minimum

This guarantees that if we can start a task, we will never immediately go negative after finishing it.

Several edge cases are important:

  • Tasks where actual == minimum

  • These are strict tasks because they leave no safety margin.

  • Tasks with very large gaps between minimum and actual

  • These tasks are difficult to start but relatively cheap to execute.

  • Single task inputs

  • The answer is simply the task's minimum.

  • Tasks with identical values

  • Sorting logic must still behave correctly.

Approaches

Brute Force Approach

The brute force solution tries every possible ordering of tasks.

For each permutation:

  1. Simulate completing tasks in that order.
  2. Compute the minimum initial energy needed for that ordering.
  3. Take the minimum across all permutations.

To compute the required initial energy for one ordering, we process tasks sequentially and ensure that before each task our energy is at least its minimum.

This approach is correct because it explores every possible ordering, so it cannot miss the optimal one.

However, it is far too slow.

If there are n tasks, there are:

n!

possible permutations.

Even for n = 15, this becomes infeasible. Since the real constraint is 10^5, brute force is completely impossible.

Key Insight for the Optimal Solution

The core challenge is determining the best order.

Consider two tasks:

A = [a1, m1]
B = [a2, m2]

Suppose we perform A before B.

To start A, we need at least m1.

After finishing A, our energy decreases by a1, so before starting B we need:

initial_energy - a1 >= m2

which means:

initial_energy >= a1 + m2

Therefore, if A comes before B, required energy is:

max(m1, a1 + m2)

Similarly, if B comes before A, required energy is:

max(m2, a2 + m1)

We should choose the order that produces the smaller requirement.

After simplifying the comparison, we obtain the greedy rule:

Sort tasks by:

(minimum - actual) descending

Why does this work?

The quantity:

minimum - actual

represents how demanding a task is relative to its cost.

  • Large difference:

  • Hard to start

  • Cheap to finish

  • Small difference:

  • Easier to start relative to energy spent

Tasks with larger gaps should be done earlier while energy is still high.

Once tasks are sorted this way, we can greedily simulate execution and compute the minimum required initial energy.

Approach Time Complexity Space Complexity Notes
Brute Force O(n! · n) O(n) Tries every possible ordering
Optimal O(n log n) O(1) or O(log n) Greedy sorting by (minimum - actual)

Algorithm Walkthrough

Step 1: Sort the Tasks

Sort all tasks in descending order of:

minimum - actual

This prioritizes tasks that require a large starting buffer.

For example:

[1,7] -> 6
[5,11] -> 6
[2,4] -> 2

Tasks with larger values come first.

Step 2: Initialize Tracking Variables

We maintain:

  • current_energy

  • Simulated remaining energy

  • required_energy

  • Minimum initial energy needed so far

Initially both are 0.

Step 3: Process Tasks in Sorted Order

For every task [actual, minimum]:

If current energy is less than minimum, we must increase our initial energy.

The extra amount needed is:

minimum - current_energy

We add this amount to both:

  • required_energy
  • current_energy

Now we can safely perform the task.

Step 4: Spend the Task Energy

After completing the task:

current_energy -= actual

Continue until all tasks are processed.

Step 5: Return the Result

At the end:

required_energy

is the smallest initial energy that makes the entire schedule feasible.

Why it works

The greedy ordering ensures that tasks with the largest startup overhead are handled first, before energy has been depleted by previous tasks.

The exchange argument proves correctness. If two adjacent tasks are not ordered by descending (minimum - actual), swapping them cannot increase the required initial energy. Repeatedly applying this swap rule transforms any optimal ordering into the greedy ordering, proving that the greedy arrangement is optimal.

Python Solution

from typing import List

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda task: task[1] - task[0], reverse=True)

        required_energy = 0
        current_energy = 0

        for actual, minimum in tasks:
            if current_energy < minimum:
                extra = minimum - current_energy
                required_energy += extra
                current_energy += extra

            current_energy -= actual

        return required_energy

The implementation begins by sorting tasks according to the greedy rule. The lambda function computes:

task[1] - task[0]

which corresponds to:

minimum - actual

in descending order.

The variable required_energy stores the total initial energy we have had to add so far. The variable current_energy simulates how much energy remains during execution.

For every task, we first check whether we have enough energy to begin it. If not, we increase both variables by exactly the missing amount.

After that, we subtract the task's actual energy cost.

Because we only ever add the minimum extra energy necessary, the final result is optimal.

Go Solution

package main

import "sort"

func minimumEffort(tasks [][]int) int {
	sort.Slice(tasks, func(i, j int) bool {
		return (tasks[i][1] - tasks[i][0]) > (tasks[j][1] - tasks[j][0])
	})

	requiredEnergy := 0
	currentEnergy := 0

	for _, task := range tasks {
		actual := task[0]
		minimum := task[1]

		if currentEnergy < minimum {
			extra := minimum - currentEnergy
			requiredEnergy += extra
			currentEnergy += extra
		}

		currentEnergy -= actual
	}

	return requiredEnergy
}

The Go implementation follows the same logic as the Python version.

The main difference is sorting syntax. Go uses sort.Slice with a custom comparator.

Go integers are sufficient because the maximum possible answer is well within 32 bit integer range:

10^5 * 10^4 = 10^9

Slices are used directly since each task is represented as a []int.

Worked Examples

Example 1

Input:

[[1,2],[2,4],[4,8]]

Step 1: Sort

Compute differences:

Task minimum - actual
[1,2] 1
[2,4] 2
[4,8] 4

Sorted order:

[[4,8],[2,4],[1,2]]

Step 2: Simulation

Task Current Energy Before Minimum Needed Extra Added Current Energy After
[4,8] 0 8 8 4
[2,4] 4 4 0 2
[1,2] 2 2 0 1

Final answer:

8

Example 2

Input:

[[1,3],[2,4],[10,11],[10,12],[8,9]]

Step 1: Sort

Task Difference
[1,3] 2
[2,4] 2
[10,11] 1
[10,12] 2
[8,9] 1

One valid sorted order:

[[1,3],[2,4],[10,12],[10,11],[8,9]]

Step 2: Simulation

Task Energy Before Minimum Extra Added Energy After
[1,3] 0 3 3 2
[2,4] 2 4 2 2
[10,12] 2 12 10 2
[10,11] 2 11 9 1
[8,9] 1 9 8 1

Total added:

3 + 2 + 10 + 9 + 8 = 32

Final answer:

32

Example 3

Input:

[[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]

All tasks have:

minimum - actual = 6

So any order works.

Simulation

Task Energy Before Minimum Extra Added Energy After
[1,7] 0 7 7 6
[2,8] 6 8 2 6
[3,9] 6 9 3 6
[4,10] 6 10 4 6
[5,11] 6 11 5 6
[6,12] 6 12 6 6

Total:

7 + 2 + 3 + 4 + 5 + 6 = 27

Final answer:

27

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) or O(log n) Depends on sorting implementation

The simulation loop itself is linear. The only expensive operation is sorting the tasks according to the greedy priority rule.

Python's Timsort uses logarithmic auxiliary stack space in practice. Go's sort implementation also uses logarithmic recursion depth.

Test Cases

from typing import List

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda task: task[1] - task[0], reverse=True)

        required_energy = 0
        current_energy = 0

        for actual, minimum in tasks:
            if current_energy < minimum:
                extra = minimum - current_energy
                required_energy += extra
                current_energy += extra

            current_energy -= actual

        return required_energy

sol = Solution()

assert sol.minimumEffort([[1,2],[2,4],[4,8]]) == 8
# Basic example from statement

assert sol.minimumEffort([[1,3],[2,4],[10,11],[10,12],[8,9]]) == 32
# Mixed task sizes and requirements

assert sol.minimumEffort([[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]) == 27
# All tasks have identical difference

assert sol.minimumEffort([[5,5]]) == 5
# Single task where actual equals minimum

assert sol.minimumEffort([[1,10]]) == 10
# Single task with large startup requirement

assert sol.minimumEffort([[1,2],[1,2],[1,2]]) == 4
# Repeated identical tasks

assert sol.minimumEffort([[2,2],[2,2],[2,2]]) == 6
# Tasks that completely consume current energy

assert sol.minimumEffort([[1,10000]]) == 10000
# Maximum minimum value

assert sol.minimumEffort([[3,5],[2,2],[1,10]]) == 10
# Large difference task should go first

assert sol.minimumEffort([[5,9],[4,8],[3,7],[2,6]]) == 14
# Descending structure

assert sol.minimumEffort([[1,2]]) == 2
# Smallest nontrivial input
Test Why
[[1,2],[2,4],[4,8]] Validates standard greedy ordering
[[1,3],[2,4],[10,11],[10,12],[8,9]] Mixed constraints and costs
[[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]] Equal differences across all tasks
[[5,5]] Single exact requirement task
[[1,10]] Large minimum requirement
[[1,2],[1,2],[1,2]] Duplicate tasks
[[2,2],[2,2],[2,2]] Energy fully depleted each step
[[1,10000]] Constraint boundary
[[3,5],[2,2],[1,10]] Validates sorting importance
[[5,9],[4,8],[3,7],[2,6]] Multiple equal gaps
[[1,2]] Minimal valid input

Edge Cases

One important edge case is when there is only a single task. In that scenario, the answer is simply the task's minimum required energy. A buggy implementation might incorrectly add the actual energy cost again or mishandle initialization. The provided implementation correctly checks whether current energy is below the minimum and adds only the required amount.

Another important case occurs when several tasks have identical values of:

minimum - actual

The greedy proof guarantees that any relative ordering among such tasks is valid. Some implementations mistakenly rely on a secondary sorting rule that is unnecessary and can complicate reasoning. This solution only sorts by the required greedy criterion, which is sufficient.

A third critical edge case involves tasks where:

actual == minimum

These tasks are strict because after completing them, energy drops significantly with no extra buffer. A buggy implementation may allow the task to start with insufficient energy due to incorrect comparison operators. This implementation uses:

if current_energy < minimum:

which correctly enforces the exact minimum threshold.

Another subtle case is when a task has an extremely large startup requirement but a tiny execution cost, such as:

[1, 10000]

If this task is delayed until later, previously consumed energy can force a much larger initial requirement. Sorting by descending (minimum - actual) correctly prioritizes these tasks early, preventing unnecessary energy inflation later in the schedule.