Pattern 13 of 27

Greedy Scheduling and Sorting

Make the locally best choice at each step when you can show it never blocks a better overall answer.

Cost: Usually O(n), or O(n log n) with a sort
Problems: 6

When to reach for it

Sorting by one key makes the decision at each step obvious.
The prompt asks for a minimum count or whether something is possible at all.
An exchange argument works: swapping in the greedy choice never makes the answer worse.

How it works

A greedy algorithm commits to a choice and never revisits it. That is only correct when some optimal answer agrees with the choice, which you usually show by arguing that replacing any other choice with the greedy one keeps the result at least as good. In practice the work is finding the right quantity to track, such as the furthest reachable index, the running fuel balance, or the last position of every letter, after which a single pass finishes the job.

The template

Written for Jump Game (write-up)

def can_jump(nums):
    reach = 0                         # furthest index reachable so far
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True

Open in the editor Trace it line by line

Six problems, in learning order

1.Jump Game IILeetCode 45Count jumps in layers: each layer ends at the furthest reach of the one before.Medium
2.Jump GameLeetCode 55Track the furthest reachable index.Medium
3.Queue Reconstruction by HeightLeetCode 406Sort by height descending, then place each person by how many taller people stand ahead.Not in the curated 370 yet.Medium
4.Task SchedulerLeetCode 621The most frequent task sets the frame; the other tasks fill the idle gaps.Medium
5.Partition LabelsLeetCode 763Extend each part until it reaches the last occurrence of every letter inside it.Medium
6.Gas StationLeetCode 134If total gas covers total cost, start just after the point where the tank went negative.Medium

What usually goes wrong

Trusting a greedy rule without testing a small counterexample; many look right and are not.
Sorting by the wrong key, for example start time where end time is needed.
Choosing greedy when overlapping subproblems mean dynamic programming is required.

Greedy Scheduling and Sorting, answered

When should I use the greedy scheduling and sorting pattern?

Sorting by one key makes the decision at each step obvious. The prompt asks for a minimum count or whether something is possible at all. An exchange argument works: swapping in the greedy choice never makes the answer worse.

What is the time complexity of greedy scheduling and sorting?

Usually O(n), or O(n log n) with a sort. In practice the work is finding the right quantity to track, such as the furthest reachable index, the running fuel balance, or the last position of every letter, after which a single pass finishes the job.

Which problem should I start with for greedy scheduling and sorting?

Start with Jump Game II (LeetCode 45, Medium). Count jumps in layers: each layer ends at the furthest reach of the one before. The six problems on this page are in learning order.