Minimum Initial Energy to Finish Tasks: Greedy Sorting

You are given an array of tasks where tasks[i] = [actual_i, minimum_i]. You have an initial energy level, and to start task i you need at least minimum_i energy. After finishing it, your energy decreases by actual_i. You can complete the tasks in any order. Return the minimum initial energy required to finish all tasks.

This is LeetCode 1665: Minimum Initial Energy to Finish Tasks, a hard problem that looks like it might need dynamic programming or backtracking but actually falls to a clean greedy sort. The trick is figuring out the right ordering, and once you see it, the solution is about ten lines of code.

Why this problem matters

This problem is a great example of greedy scheduling. Many interview problems ask you to find the optimal order to process items under resource constraints. The pattern here, sort by some derived quantity and greedily compute the answer, appears in problems like task scheduling, job sequencing, and activity selection.

The key skill is recognizing what to sort by. In this problem, the natural instinct might be to sort by minimum energy or by actual cost. Neither works. You need to sort by the gap between them, the surplus minimum_i - actual_i. Understanding why that gap matters builds intuition for other greedy ordering problems.

The brute force approach

The most obvious solution tries every permutation of tasks and finds the one that requires the least starting energy.

from itertools import permutations

def minimum_effort_brute(tasks):
    best = float("inf")
    for perm in permutations(tasks):
        energy = 0
        cur = 0
        for actual, minimum in reversed(perm):
            cur = max(minimum, cur + actual)
        best = min(best, cur)
    return best

This works, but there are n! permutations. For n = 10 that is about 3.6 million orderings. For the problem constraint of n up to 10^5, this is completely infeasible. We need to find the optimal ordering without trying them all.

The key insight: sort by surplus descending

Each task has two properties: actual (what it costs) and minimum (what you need to start). The difference minimum - actual is the surplus, the amount of energy the task "locks up" without consuming. When you finish a task, you lose actual energy, but you needed minimum to even begin. The leftover minimum - actual is energy you had to have on hand but did not spend.

If you do a high-surplus task early, you need that extra buffer sitting idle in your energy pool for that task. But if you do it later, some of that buffer might already be covered by the energy you would have needed anyway for subsequent tasks. In other words, tasks with larger surpluses are more expensive to postpone because their buffer requirements cannot be amortized by the remaining workload.

Sorting by minimum - actual in descending order puts the greediest tasks first, when you have the most energy to spare.

Walking through it step by step

Let's trace through tasks = [[1,2],[2,4],[4,8]]. The surpluses are 1, 2, and 4. After sorting by surplus descending, the order becomes [4,8], [2,4], [1,2].

Starting with energy 8, every task's minimum threshold is met exactly when needed. The algorithm works backward from the last task to compute the minimum starting energy, but the forward simulation confirms it.

The greedy solution

Here is the complete solution in Python:

def minimum_effort(tasks):
    tasks.sort(key=lambda t: t[1] - t[0], reverse=True)
    energy = 0
    cur = 0
    for actual, minimum in tasks:
        energy += actual
        cur = max(energy, minimum)
        energy = cur
    return energy

Here is what each piece does:

1. Sort tasks by minimum - actual in descending order. This ensures high-surplus tasks come first.
2. Initialize energy = 0 and cur = 0. We will accumulate the minimum starting energy as we go.
3. For each task, add actual to energy (we must pay this cost). Then set energy = max(energy, minimum) because we also need at least minimum energy before doing this task.
4. Return energy, which now holds the minimum initial energy to complete all tasks in this order.

There is an equivalent and arguably cleaner way to think about it by iterating in reverse:

def minimum_effort(tasks):
    tasks.sort(key=lambda t: t[1] - t[0], reverse=True)
    cur = 0
    for actual, minimum in reversed(tasks):
        cur = max(minimum, cur + actual)
    return cur

This builds the answer from the last task backward. For the last task, you need at least minimum. For each earlier task, you need at least minimum for that task, or enough to cover actual plus whatever the remaining tasks need, whichever is larger.

Why sorting by surplus works

Consider two tasks A and B. If you do A before B, the total energy needed is:

• At least minimum_A to start A.
• After A, you have energy - actual_A left, and you need at least minimum_B for B.

If you do B before A, the roles swap. It turns out that doing A first is better when minimum_A - actual_A > minimum_B - actual_B. The proof is a standard exchange argument: swapping two adjacent tasks in any optimal order where A has higher surplus but comes after B never increases the total energy. Therefore, sorting by surplus descending gives the optimal order.

Complexity analysis

After sorting, the loop is a single O(n) pass. The sort is the bottleneck. Since you need to consider all tasks at least once, O(n log n) is optimal for a comparison-based approach.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy exchange argument

The pattern of proving an ordering is optimal by showing that swapping any two adjacent out-of-order elements never improves the solution:

items.sort(key=lambda x: derived_quantity(x), reverse=True)
result = 0
for item in items:
    result = update(result, item)
return result

In this problem, the derived quantity is minimum - actual. In other problems it might be deadline minus duration, or profit-to-weight ratio. The skeleton is the same: derive a comparison key, sort by it, and scan once. This pattern appears in fractional knapsack, job scheduling with deadlines, and weighted activity selection.

2. Greedy accumulation with threshold

The pattern of maintaining a running resource level and ensuring it meets a threshold at each step:

resource = 0
for cost, threshold in sorted_items:
    resource += cost
    resource = max(resource, threshold)
return resource

You accumulate costs and enforce minimums as you go. The max operation ensures the threshold constraint is never violated. This same skeleton appears in problems where you need to find the minimum starting value to keep a running total above some floor, like minimum initial points in a dungeon game.

Edge cases

Before submitting, make sure your solution handles these:

• Single task [[5, 10]]: you need exactly 10 energy. The sort is a no-op, and the answer is just minimum.
• All tasks have equal surplus [[1, 3], [2, 4], [3, 5]]: every surplus is 2. Any order works. The algorithm picks an arbitrary consistent order and still gives the correct answer.
• Zero surplus tasks [[3, 3], [5, 5]]: surplus is 0 for all. You need 3 + 5 = 8 energy. No extra buffer is wasted.
• One very large surplus [[1, 100], [50, 50]]: the [1, 100] task must come first (surplus 99 vs 0). Starting energy is 101: you need 100 to start the first task, spend 1, have 99 left, which exceeds 50 for the second task.
• actual equals minimum for all [[a, a], ...]: this degenerates to needing the sum of all actual costs. Every task consumes exactly what it requires with no surplus.

The greedy solution handles all of these without special-case logic.

Common mistakes

1. Sorting by the wrong key. Sorting by minimum descending or actual ascending does not produce the optimal order. The correct key is minimum - actual (surplus) descending. The exchange argument proves this.

2. Forgetting the max operation. When accumulating energy, you must take max(energy, minimum) at each step, not just add actual. Without the max, you miss the threshold constraint and undercount the required energy.

3. Processing in the wrong direction. The forward accumulation and backward accumulation formulations both work, but mixing them up produces wrong answers. If iterating forward, accumulate actual and apply max with minimum. If iterating backward (reversed), set cur = max(minimum, cur + actual).

4. Confusing actual with minimum. The problem uses actual for the energy consumed and minimum for the threshold to begin. Swapping them in your sort key or accumulation gives the wrong answer.

From understanding to recall

You have read the greedy solution and the exchange argument makes sense. Sort by surplus, scan once, done. But can you write it from scratch in an interview without looking at it?

The details matter: the sort key is minimum - actual not actual - minimum, the order is descending not ascending, and the accumulation uses max(energy, minimum) not just addition. These are small but critical, and they slip under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the sort-and-scan greedy loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "choose the optimal task order to minimize starting resources" and the code flows out without hesitation.

The greedy exchange argument pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Jump Game - Another greedy problem where a single-pass scan replaces brute-force simulation
• Gas Station - Greedy with reset, another problem where choosing the right starting point avoids exhaustive search
• Candy - Two-pass greedy constraint satisfaction, a related technique for problems with bidirectional dependencies

CodeBricks breaks the minimum initial energy to finish tasks LeetCode problem into its greedy exchange argument and threshold accumulation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy scheduling question shows up in your interview, you do not think about it. You just write it.