Greedy Algorithms

Greedy is the most dangerous pattern: the code is short and obvious, which makes it feel right even when it is wrong. The skill is not writing greedy code — it is knowing when greedy is actually correct.

The idea

A greedy algorithm makes a sequence of choices, each the best available at that moment, and never backtracks. Compare that with dynamic programming, which explores all choices and remembers sub-results. Greedy is strictly simpler — one pass, no table — but it only produces the right answer when the problem has the greedy-choice property: taking the locally-best option never rules out the global optimum.

How do you know greedy works? Two practical tests:

1. Exchange argument. Assume an optimal solution differs from the greedy one. Show you can swap in the greedy choice without making the solution worse. If you always can, greedy is optimal.
2. Try to break it on small cases. Hand-run three or four tiny inputs, especially adversarial ones. If greedy ever loses, you need DP instead.

Worked example: interval scheduling

Given meetings with start/end times, select the maximum number that don’t overlap. The greedy insight: always take the meeting that finishes earliest, because finishing early leaves the most room for the rest. Sort by end time, then sweep:

def max_meetings(intervals):
    intervals.sort(key=lambda x: x[1])          # by END time
    count = 0; end = float('-inf')
    for s, e in intervals:
        if s >= end:                            # no overlap → take it
            count += 1; end = e
    return count
# max_meetings([[1,3],[2,4],[3,5],[0,2]]) -> 3

The exchange argument: if some optimal schedule skipped the earliest-finishing meeting, you could swap it in for whatever it chose first and never lose a slot. So greedy is optimal here.

Worked example: jump game

Each value is the maximum jump length from that index. Can you reach the last index? Track the furthest index reachable so far; if you ever stand beyond it, you’re stuck.

def can_jump(nums):
    reach = 0
    for i, x in enumerate(nums):
        if i > reach:            # can't even get here
            return False
        reach = max(reach, i + x)
    return True
# can_jump([2,3,1,1,4]) -> True
# can_jump([3,2,1,0,4]) -> False

O(n) time, O(1) space — no DP table needed, because extending the furthest reach is always the best local move.

Worked example: gas station

You have gas[i] at station i and it costs cost[i] to reach the next. Find a start from which you can loop once. If the total gas is at least the total cost, a solution exists; and whenever the running tank drops below zero, no station in the stretch you just drove can be the answer, so restart from the next one:

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                 # this stretch fails → restart after it
            start = i + 1; tank = 0
    return start
# can_complete_circuit([1,2,3,4,5], [3,4,5,1,2]) -> 3

Step-by-step walkthrough

Trace Jump Game on [2, 3, 1, 1, 4]. The greedy choice: track only the farthest index reachable so far. If we ever stand on an index beyond it, we’re stuck.

By index 1 the reach already covers the last index, so the answer is True — in one pass with O(1) memory. We never had to decide which jump to take; the farthest reach captures every possibility at once, which is why greedy is correct here.

When to reach for it

Signals: “maximum / minimum number of …”, interval problems (scheduling, merging, non-overlapping, arrows), “can you reach / is it possible”, “least/most to do X”, and anything that smells like sort-then-sweep or always pick the biggest/smallest/earliest remaining. Heaps often pair with greedy when the “best remaining” changes as you go (see Lesson 14).

Pitfalls

• Assuming greedy works without proof. This is the greedy bug. Coin change makes the point: greedy (take the biggest coin that fits) is optimal for [1,5,10,25] but wrong for [1,3,4] making 6 (greedy gives 4+1+1, optimum is 3+3). When in doubt, it’s DP.
• Wrong sort key. Interval problems hinge on sorting by the right field — by end time for “maximum non-overlapping”, by start for merging. Pick deliberately.
• Ties and edge cases. Decide whether start == end counts as overlapping, and handle empty input and single elements.

Recap

Greedy builds the answer by taking the best local choice and never looking back — simpler and faster than DP, but only correct when the greedy-choice property holds (prove it with an exchange argument or break it on small cases). Classics: interval scheduling (sort by end time), jump game (track furthest reach), gas station (reset on negative tank). Signal words: max/min number of, intervals, can you reach, sort-then-sweep. Always ask first: does greedy actually work here, or do I need DP?

Practice: 11 solved problems on greedy → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 23 — Advanced Graphs, weighted shortest paths and minimum spanning trees.