The Project | About Us | Contribute | Donations | License

HOME

In the previous lesson we learned to chop problems up with divide and conquer. The second great strategy of the module has the opposite temperament: instead of solving everything and then deciding, a greedy algorithm builds the solution step by step, taking at each moment the decision that looks best right now, without looking back and without computing the future consequences. This impatience produces simple, blazing-fast algorithms... that are sometimes provably optimal and other times fail spectacularly without warning. In RutaBus we already ran into a greedy without knowing it: the supervisor_route from 01-02, that nearest-neighbor heuristic. In this lesson we will learn the anatomy of a greedy algorithm, solve a real trip-assignment problem, watch a greedy fail with our own eyes, and — most importantly — learn to tell when one can be trusted.

The idea: a locally optimal, irrevocable decision
Anatomy of a greedy algorithm
RutaBus example: maximum number of trips for one bus
Why it works: an informal proof
When greedy fails: two counterexamples
How to recognize whether a problem admits greedy
Famous greedy algorithms

The idea: a locally optimal, irrevocable decision

A greedy algorithm is characterized by two traits:

Locally optimal choice: at each step it picks the candidate that maximizes (or minimizes) an immediate criterion, without simulating the future.
Irrevocability: a decision once taken is never revisited. There is no going back — exactly the opposite of the backtracking we will see in 03-04.

This combination explains its two faces:

Good face	Bad face
Very fast: each element is decided once, typically O(n log n) due to the prior sorting	The sum of local optima is not always the global optimum
Easy to implement and to understand	The failure is silent: they return a solution, just not the best one
Little memory: they store no alternatives	They demand a proof (or at least a solid argument) of optimality

Anatomy of a greedy algorithm

Almost all greedy algorithms share four pieces. It pays to identify them explicitly before writing code:

Candidate set: the elements to choose from (trips, coins, stops...).
Selection function: the greedy criterion that decides which candidate to take next ("the one that finishes earliest", "the largest coin", "the nearest stop").
Feasibility test: can I add this candidate to the partial solution without violating the constraints?
Solution: the construction ends when the candidates run out or the solution is complete.

In pseudocode, the universal skeleton:

solution = empty
candidates = sort(candidates, by the selection function)
for each candidate c in order:
    if adding c to solution is feasible:
        add c to solution        # irrevocable: never removed
return solution

All the ingenuity lies in the sorting step: choosing the selection function well is designing the algorithm. With the right function, greedy is optimal; with a plausible but wrong one, it is just a heuristic (remember the exact-vs-heuristic distinction from 01-02).

RutaBus example: maximum number of trips for one bus

The problem. RutaBus has a single reinforcement bus and a list of trips requested for tomorrow, each with a start time and an end time (in minutes since midnight). The bus can only do one trip at a time. Goal: assign it the maximum number of trips with no overlaps. (This is the RutaBus version of the classic activity selection problem.)

# (name, start, end) — minutes since 00:00
trips = [
    ("Main Square -> North Station",   540, 600),   # 09:00-10:00
    ("North Station -> Hospital",      570, 630),   # 09:30-10:30
    ("Hospital -> River Park",         600, 660),   # 10:00-11:00
    ("River Park -> Main Square",      615, 675),   # 10:15-11:15
    ("Main Square -> Hospital",        660, 720),   # 11:00-12:00
    ("Hospital -> North Station",      690, 780),   # 11:30-13:00
]

Before seeing the solution, think: which selection function would you use? Reasonable candidates: the shortest trip first, the one that starts earliest, the one with the fewest conflicts... They all sound good and they all fail in some case. The correct one is less intuitive: the one that finishes earliest.

def assign_trips(trips):
    """Max number of non-overlapping trips for one bus (greedy).
    Returns the list of assigned trips."""
    # Selection function: sort by ascending END time
    sorted_items = sorted(trips, key=lambda t: t[2])

    assigned = []
    last_end = 0                      # time at which the bus becomes free

    for name, start, end in sorted_items:
        if start >= last_end:         # feasibility test: no overlap
            assigned.append((name, start, end))   # irrevocable decision
            last_end = end
    return assigned

for t in assign_trips(trips):
    print(t[0])
# Main Square -> North Station    (09:00-10:00)
# Hospital -> River Park          (10:00-11:00)
# Main Square -> Hospital         (11:00-12:00)

Line-by-line explanation:

sorted(..., key=lambda t: t[2]): materializes the selection function. Cost O(n log n), which will dominate the total (02-01).
last_end: the minimum state we need to remember — when the bus becomes free. Note the use of a single variable: O(1) auxiliary space plus the output (02-02).
if start >= last_end: the feasibility test. A trip is compatible if it starts when the bus is already free.
The append is the irrevocable decision: we never reconsider an accepted trip nor recover a rejected one.
The loop goes through the candidates once: O(n). Total: O(n log n), versus the exponential cost of trying every subset of trips.

Result: 3 trips. No combination achieves 4 — and this is no accident, as we are about to argue.

Why it works: an informal proof

The classic argument is called the exchange argument, and it is worth internalizing, because it is the standard tool for justifying a greedy algorithm:

Let g be the first trip the greedy picks: the one that finishes earliest of all.
Take any optimal solution OPT. If OPT does not contain g, look at the first trip of OPT (call it x). Since g finishes at or before any trip — including x —, we can replace x with g in OPT without creating overlaps: g frees the bus even earlier than x, so everything that fit after x still fits after g.
The modified solution has the same size as OPT, so it is still optimal and it starts like the greedy does.
Removing g and the trips incompatible with it leaves an identical but smaller subproblem ("maximum number of trips starting after last_end"), to which the same reasoning applies again and again.

Conclusion: the greedy choice never takes us away from an optimum. Note the logic: we are not saying that greedy is the only optimal solution, but that there always exists an optimum that takes the greedy decision — and that is enough.

This argument also explains why "finishes earliest" is the key: finishing early leaves the maximum possible room for the future. The rival criteria lack that property: the shortest trip can sit "crosswise", blocking two compatible long ones, and the one that starts earliest can be endless and eat up the whole morning.

When greedy fails: two counterexamples

Counterexample 1: non-canonical coin change

The top-up bills for the RutaBus card are worth 1, 3 and 4 euros (a deliberately exotic system). We want to pay an amount with the minimum number of bills. The natural greedy — "always take the largest bill that fits" — fails:

def greedy_change(amount, values=(4, 3, 1)):
    used = []
    for v in values:                 # from largest to smallest
        while amount >= v:
            used.append(v)
            amount -= v
    return used

print(greedy_change(6))   # [4, 1, 1]  -> 3 bills
# Actual optimum: [3, 3]  -> 2 bills

For 6 €, the greedy takes the 4 (locally optimal) and dooms itself to finish with two 1-coins. The irrevocable decision of grabbing the 4 destroys the possibility of using 3+3. With the euro system (1, 2, 5, 10, 20, 50...) the greedy is optimal — the system is said to be canonical —, which illustrates something uncomfortable: the same algorithm is exact or incorrect depending on the problem's data. That is why a greedy without an optimality argument is a gamble. (The general version of coin change is solved with guarantees by dynamic programming, the strategy of 03-03.)

Counterexample 2: reunion with `supervisor_route`

In 01-02 we wrote supervisor_route: the supervisor visits all the stops by always going to the nearest unvisited one. Now we have the vocabulary to diagnose it: it is a textbook greedy — candidates: unvisited stops; selection: minimum distance; feasibility: don't repeat a stop. And we already said back then that it is a heuristic: it gives reasonable routes, not the shortest route.

Watching it fail is easy with stops on a straight line (positions in km): the supervisor starts from km 0 and must visit the stops at km 1, 2 and −1.5.

Greedy (nearest neighbor): the closest to 0 is the one at km 1 → then the one at 2 (1 km away) → and finally the one at −1.5 (3.5 km away). Total: 1 + 1 + 3.5 = 5.5 km.
Optimum: go "against the current" first: 0 → −1.5 (1.5 km) → 1 (2.5 km) → 2 (1 km). Total: 5 km.

The greedy loses by going for the comfortable option first and leaving the long return leg for the end: every local choice was impeccable and the total, suboptimal.

The moral is twofold. First: greedy fails when a comfortable decision now creates an unavoidable extra cost later. Second: a non-optimal greedy is not garbage — as a heuristic, supervisor_route gives decent solutions in O(n²) for a problem (the traveling salesman's) whose exact solution is exponential. Knowing that it isn't optimal, and deciding whether it's good enough for us, is exactly the kind of professional judgment this course trains.

How to recognize whether a problem admits greedy

There is no foolproof recipe, but there are two properties that "greedy-friendly" problems exhibit (we state them informally; their rigorous treatment belongs to advanced texts):

Greedy-choice property: there exists a locally optimal choice that is part of some globally optimal solution — that is, deciding now, without looking at the future, does not close the door on the optimum. It is typically checked with an exchange argument like the one in the previous section.
Optimal substructure: after taking the greedy decision, what remains is a subproblem of the same type whose optimal solution, joined to the decision taken, yields the global optimum. (This property will reappear in 03-03: dynamic programming also demands it. The difference: DP explores several possible decisions and greedy bets everything on one.)

Practical checklist before trusting a greedy:

Can I formulate a clear selection function?
Do I have an exchange argument, even an informal one, that the greedy choice does not rule out the optimum?
Have I actively looked for small counterexamples (3-6 elements, edge cases)?
If I can't manage 2 and 3: is it good enough as a heuristic, or does the problem demand the exact optimum (→ DP in 03-03 or backtracking in 03-04)?

Famous greedy algorithms

Algorithm	Problem	Optimal?	Where
Dijkstra	Shortest path from a source in a graph with non-negative weights	Yes (a greedy with a proof)	04-05
Kruskal / Prim	Minimum spanning tree (connect all the stops with the least cable/road)	Yes	(mention only)
Huffman	Minimum-length compression codes	Yes	(mention only)
Activity selection	Maximum number of non-overlapping tasks	Yes (seen today)	03-02
Nearest neighbor	Route visiting all stops (traveling salesman)	No: heuristic	01-02 / today
Coin change	Minimum number of coins	Only in canonical systems	today

Dijkstra deserves a note: it is the proof that "greedy" does not mean "approximate". Always choosing the unprocessed stop nearest to the source is optimal for shortest paths — we will prove it and implement it in 04-05, when the RutaBus network finally becomes a weighted graph.

Common Mistakes and Tips

Assuming optimality without an argument. "It sounds reasonable" is not a proof. Coin change with (1, 3, 4) sounds just as reasonable and fails. Always demand an exchange argument or exhaustively tried counterexamples.
Picking the wrong selection function. In the trips problem, three plausible criteria fail and only "finishes earliest" works. Test each candidate criterion against small examples designed with malice.
Forgetting the sorting in the analysis. The greedy loop is O(n), but the prior sorted makes it O(n log n). Don't announce costs that your own code contradicts (02-01).
Confusing "greedy fails" with "greedy is useless". A greedy heuristic with empirical guarantees can be the best engineering option when the exact algorithm is exponential. Document that it is a heuristic and move on.
Modifying the already-built solution. If you catch yourself "removing" accepted elements, you are no longer writing a greedy: you are improvising an uncontrolled backtracking. Rethink the strategy (03-04).

Exercises

Exercise 1

RutaBus wants to install the minimum number of charging points along an avenue so that every stop has a point within 500 m. The stop positions (in meters) are in a sorted list, e.g. [100, 300, 850, 900, 1800]. Design a greedy: state the candidates, the selection function and the feasibility test, and implement it. Hint: process the stops from left to right and place each point as far to the right as possible.

Exercise 2

For the trips problem, prove with a concrete counterexample (3-4 trips with times) that the selection function "the shortest trip first" is not optimal.

Exercise 3

The reinforcement bus has a tank good for 300 km. Along the route there are gas stations at km [90, 150, 230, 350, 480] and the route is 520 km long. Write a greedy that computes the minimum number of refuels (starting with a full tank) and reason informally why its greedy choice is safe.

Solutions

Solution 1

Candidates: possible positions for charging points. Selection: for the leftmost uncovered stop, place the point at stop + 500 (as far right as still covers it). Feasibility: every stop must end up within ≤ 500 m of some point.

def charging_points(stops_m, radius=500):
    points = []
    i, n = 0, len(stops_m)
    while i < n:
        point = stops_m[i] + radius       # as far right as possible
        points.append(point)
        # skip all the stops this point already covers
        while i < n and stops_m[i] <= point + radius:
            i += 1
    return points

print(charging_points([100, 300, 850, 900, 1800]))  # [600, 2300]

With [100, 300, 850, 900, 1800]: the point at 600 covers 100, 300, 850 and 900 (all within ≤ 500 of 600... 100 is at exactly 500, inside); the point at 2300 covers 1800. Total: 2 points. Exchange argument: any optimal solution needs some point covering the first stop; moving it up to stops[0] + 500 uncovers no one on the left (there is no one) and can only cover more stops on the right. Cost: O(n).

Solution 2

Trips: A = (10:00-12:00), B = (11:45-12:15), C = (12:10-14:00). The shortest is B (30 min); the "shortest first" greedy picks it, and B overlaps both A (11:45 < 12:00) and C (12:10 < 12:15): both get discarded and the total is 1 trip. However, A and C are compatible with each other (A ends at 12:00 ≤ 12:10): the optimum is 2. B sits "crosswise", blocking two compatible trips — exactly the flaw we anticipated in the lesson. Check that the correct criterion, "finishes earliest", picks A and then C and reaches the optimum.

Solution 3

Greedy selection: don't refuel until it is unavoidable and, then, do it at the farthest reachable gas station we have left behind.

def min_refuels(stations, total_km, tank_range=300):
    refuel_stops = []                     # where we refuel
    position = 0                          # last refuel (or departure)
    points = stations + [total_km]        # the destination closes the route

    for point in points:
        if point - position > tank_range: # can't reach 'point' from 'position'
            # refueling is unavoidable: at the last reachable station
            reachable = [s for s in stations
                         if position < s <= position + tank_range]
            if not reachable:
                return None               # gap larger than the range
            position = max(reachable)     # the farthest reachable one
            refuel_stops.append(position)
            if point - position > tank_range:
                return None               # not even refueling gets us there
    return refuel_stops

print(min_refuels([90, 150, 230, 350, 480], 520))  # [230]

Trace with range 300: from km 0 we can reach up to 300, so 90, 150 and 230 are passed by; 350 is no longer reachable → refueling is unavoidable, and of the reachable stations (90, 150, 230) we pick the farthest: 230. From 230 we can reach km 530 ≥ 520, so we arrive at the destination passing by 350 and 480. Result: 1 refuel. Exchange argument: when refueling is inevitable, any optimal plan refuels at some reachable station; replacing it with the farthest one cannot leave us stranded (it was also reachable) and leaves the tank full farther ahead, covering an equal or greater subsequent stretch. The greedy choice never moves us away from the optimum. (The search for reachable inside the loop is O(n); with two indices it stays O(n) overall — a nice optional refinement.)

Conclusion

Greedy algorithms build the solution through local, irrevocable decisions: candidates + selection function + feasibility test, almost always with an O(n log n) sort as the only relevant cost. We have seen the strategy shine in trip assignment — with its exchange argument: choosing what finishes earliest never closes the door on the optimum — and fail in coin change with (1, 3, 4) and in our old acquaintance supervisor_route, which today we have renamed to what it always was: a greedy heuristic. The underlying lesson: greedy demands proving (or at least arguing and hunting for counterexamples), because its failure is silent. And what do we do when the problem has optimal substructure but the greedy choice fails — when 6 € is better paid with 3+3 than by starting with the 4? We need a strategy that, instead of betting everything on one decision, explores all possible decisions while reusing the repeated computations — the idea of spending memory to avoid repeating work that we noted in 02-02 with build_index. That strategy has a name of its own and stars in the next lesson: dynamic programming.

Greedy Algorithms

Contents

The idea: a locally optimal, irrevocable decision

Anatomy of a greedy algorithm

RutaBus example: maximum number of trips for one bus

Why it works: an informal proof

When greedy fails: two counterexamples

Counterexample 1: non-canonical coin change

Counterexample 2: reunion with `supervisor_route`

How to recognize whether a problem admits greedy

Famous greedy algorithms

Common Mistakes and Tips

Exercises

Exercise 1

Exercise 2

Exercise 3

Solutions

Conclusion

Algorithm Analysis and Design Course

Module 1: Introduction to Algorithms

Module 2: Algorithm Analysis

Module 3: Algorithm Design Strategies

Module 4: Classic Algorithms

Module 5: Algorithm Optimization

Module 6: Practice and Exercises

Greedy Algorithms

Contents

The idea: a locally optimal, irrevocable decision

Anatomy of a greedy algorithm

RutaBus example: maximum number of trips for one bus

Why it works: an informal proof

When greedy fails: two counterexamples

Counterexample 1: non-canonical coin change

Counterexample 2: reunion with supervisor_route

How to recognize whether a problem admits greedy

Famous greedy algorithms

Common Mistakes and Tips

Exercises

Exercise 1

Exercise 2

Exercise 3

Solutions

Conclusion

Algorithm Analysis and Design Course

Module 1: Introduction to Algorithms

Module 2: Algorithm Analysis

Module 3: Algorithm Design Strategies

Module 4: Classic Algorithms

Module 5: Algorithm Optimization

Module 6: Practice and Exercises

Counterexample 2: reunion with `supervisor_route`