The Greedy Algorithm Approach

A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now, and never reconsidering.

No backtracking, no lookahead, no exploring alternatives. Decide, commit, move on.

Characteristics

The syllabus asks for these.

1. Makes a locally optimal choice at each step. "Best" is defined by a rule you choose in advance — shortest, cheapest, largest.

2. Never revisits a decision. Once made, a choice is final.

3. Greedy-choice property. For the algorithm to be correct, a locally optimal choice must lead to a globally optimal solution. This holds for some problems and not others — and it is the whole question.

4. Optimal substructure. After a choice is made, what remains is a smaller instance of the same problem.

5. Fast and simple. Usually one pass, often after sorting.

Motivations for the greedy approach

1. Speed. Typically the cost of a sort plus one pass — far cheaper than examining combinations.

2. Simplicity. Short to write, easy to explain, hard to get subtly wrong.

3. Low memory. No table of sub-answers, no recursion stack.

4. Sometimes provably optimal. Where the greedy-choice property holds, you get the best answer and the speed.

5. A good approximation when it isn't. Where it does not hold, greedy often lands close — as nearest-neighbour did for the travelling salesman in Module 1, about 3% above optimal.

The syllabus example: maximum tasks in limited time

Given an array of positive integers, each the completion time of a task, find the maximum number of tasks that can be completed in the limited time available.

The greedy rule: always take the shortest remaining task.

def max_tasks(times, limit):
    done = 0
    spent = 0
    for t in sorted(times):          # shortest first
        if spent + t <= limit:
            spent += t
            done += 1
        else:
            break                    # nothing longer will fit either
    return done

Tasks [3, 1, 7, 2, 5] with 8 hours:

3 tasks. No arrangement does better — 1+2+3 = 6 uses the least time for three tasks, and any three including 5 or 7 exceeds 8.

Why this greedy rule is provably right

The objective is the number of tasks, not their total value. Taking the shortest available task always leaves the most time for the rest. Formally: if an optimal solution does not include the shortest task, you can swap the shortest in for one of its tasks without making things worse.

This is the exception, not the rule. Change the problem slightly — ask for maximum value rather than maximum count — and taking the shortest first is no longer correct.

Where greedy fails

The classic counter-example is making change.

Coins [1, 3, 4], target 6.

Greedy takes the largest coin that fits:

• Take 4 → remaining 2
• Take 1 → remaining 1
• Take 1 → remaining 0
• 3 coins

But 3 + 3 = 6 is 2 coins. Greedy was wrong, because committing to the 4 destroyed the better option.

Note that with normal currency (1, 2, 5, 10, 20, 50) greedy is optimal. The rule's correctness depends on the coin set — so "it works on the examples I tried" proves nothing.

Greedy versus dynamic programming

The syllabus asks for this comparison.

Dynamic programming succeeds on the coin problem precisely because it does not commit: it computes the best way to make every amount up to the target, so 6 is answered by comparing every first coin rather than assuming the largest.

The rule of thumb: try greedy first, since it is simpler and faster. But you must be able to argue why the greedy choice is safe. If you cannot, and correctness matters, use dynamic programming.