Greedy Algorithms: When Locally Best Wins Globally

A greedy algorithm makes the choice that looks best right now, and never reconsiders. It is the simplest possible decision strategy: at each step, take the most attractive option locally and commit. The surprising fact is that for a useful family of problems, this short-sighted strategy gives a globally optimal answer.

This post is about recognising that family — and recognising when you’ve stepped outside it.

What makes a problem “greedy-solvable”?

Two properties have to hold:

1. Greedy choice property — the locally optimal choice is part of some globally optimal solution.
2. Optimal substructure — once you make that choice, the remaining problem is the same kind of problem on smaller input.

If both hold, you can prove correctness by induction. The hard part is the first one — convincing yourself the locally best choice doesn’t paint you into a corner later.

The professional name for the structures where greedy provably works is matroids. You don’t need the theory, but the intuition is worth remembering: greedy works when “swapping in” a better local choice never breaks anything you already committed to.

The classic example: activity selection

You have a set of activities, each with a start and end time. Pick the maximum number that don’t overlap.

The greedy rule: always pick the activity that ends earliest among those still compatible with what you’ve picked.

activities (sorted by end time):
A: |==|              (0, 2)    pick A
B:    |==|           (2, 4)    pick B  (starts at 2, A ended at 2)
C:   |====|          (1, 5)    skip   (overlaps B)
D:       |==|        (4, 6)    pick D  (starts at 4, B ended at 4)
E:        |======|   (5, 9)    skip   (overlaps D)
F:            |==|   (7, 9)    pick F
result: { A, B, D, F }   count = 4

def activity_selection(activities):
    # activities: list of (start, end)
    activities.sort(key=lambda a: a[1])
    chosen = []
    last_end = float("-inf")
    for s, e in activities:
        if s >= last_end:
            chosen.append((s, e))
            last_end = e
    return chosen

print(activity_selection([(0, 2), (2, 4), (1, 5), (4, 6), (5, 9), (7, 9)]))
# output: [(0, 2), (2, 4), (4, 6), (7, 9)]

Time: O(n log n) dominated by the sort. Space: O(1) beyond the output.

The exchange argument (sketched)

Suppose there is some optimal solution O that doesn’t include the earliest-finishing activity A. Then O includes some activity A' whose end time is >= A.end. Swap A' for A: the new schedule is still valid (since A ends no later than A', anything O did after A' is still fine after A), and the size is unchanged. So our greedy choice was never worse than optimal — it can be substituted in. Inductively, the whole greedy schedule matches an optimal one in size.

This pattern — “you can always exchange the optimal’s choice for the greedy’s choice without loss” — is the exchange argument, and it is the proof template for most greedy algorithms.

When greedy fails: coin change

You have coins of denominations [1, 3, 4] and want to make 6 using the fewest coins.

Greedy says: take the largest coin <= 6, which is 4. Then take the largest <= 2, which is 1. Then another 1. Total: 4 + 1 + 1, three coins.

But the optimal is 3 + 3, two coins.

Greedy fails here because committing to 4 rules out the use of two 3s. The greedy choice property does not hold for arbitrary coin systems. (It happens to hold for the US system [1, 5, 10, 25], which is why making change feels easy.)

The fix for general coin change is dynamic programming — a topic for another post. The lesson for now: always sanity-check greedy with a small adversarial example before trusting it.

When to suspect greedy

Look for these signals in a problem:

• Schedule / interval problems — activity selection, meeting rooms, minimum arrows.
• Pick / skip decisions where committing doesn’t lock out the rest.
• An objective like “minimum number of X” or “maximum number of Y” with a natural sort order.
• The problem has a clear monotonic structure — sorting by something makes the rest trivial.

And red flags that mean greedy probably won’t work:

• The decision depends on later context you can’t see yet.
• Small adversarial inputs break your rule.
• The problem screams “try every combination” — that is usually backtracking or DP.

Practice problems

1. Jump Game

Given an array where nums[i] is the max jump from index i, can you reach the last index?

Greedy: walk left to right, tracking the furthest index reachable.

def can_jump(nums):
    reach = 0
    for i, n in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + n)
    return True

print(can_jump([2, 3, 1, 1, 4]))
# output: True
print(can_jump([3, 2, 1, 0, 4]))
# output: False

2. Gas Station

You have n stations in a circle with gas[i] and cost[i]. Find the starting station that lets you complete the loop, or return -1.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))
# output: 3

The greedy claim: if you fail somewhere between start and i, no station in that range can be a valid start — they all fail at or before i. So you jump start to i + 1 directly. Total time: O(n).

3. Activity Selection

Shown above. Sort by end time, sweep, accept compatible activities.

4. Fractional Knapsack

Items have values and weights. You can take fractions. Maximise value for a given weight capacity.

def fractional_knapsack(items, capacity):
    # items: list of (value, weight)
    items.sort(key=lambda i: i[0] / i[1], reverse=True)
    total = 0.0
    for v, w in items:
        if capacity >= w:
            total += v
            capacity -= w
        else:
            total += v * (capacity / w)
            break
    return total

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))
# output: 240.0

Sort by value-per-weight and take the best ratio first. Crucially, this works because fractions are allowed. The integer version (0/1 knapsack) is NOT solvable by greedy — that one is DP.

5. Minimum Number of Arrows to Burst Balloons

Each balloon is an interval [x_start, x_end]. One arrow at position x bursts every balloon whose interval contains x. Find the minimum number of arrows.

def find_min_arrows(points):
    if not points:
        return 0
    points.sort(key=lambda p: p[1])
    arrows = 1
    end = points[0][1]
    for s, e in points[1:]:
        if s > end:
            arrows += 1
            end = e
    return arrows

print(find_min_arrows([[10, 16], [2, 8], [1, 6], [7, 12]]))
# output: 2

This is structurally identical to activity selection: sort by end, take an arrow at the earliest end-point, skip anything that overlaps.

6. Best Time to Buy and Sell Stock II

You can buy and sell as many times as you want (but only hold one share at a time). Maximise profit.

def max_profit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

print(max_profit([7, 1, 5, 3, 6, 4]))
# output: 7

The greedy insight: any profitable multi-day rise can be decomposed into the sum of single-day rises, so just collect every up-step.

A workflow for greedy problems

1. State the greedy rule in one sentence (“always pick the activity that ends earliest”).
2. Sanity-check on small inputs — try 2, 3, 4 elements with adversarial ordering.
3. Sketch the exchange argument — could the optimal solution be transformed into one using your greedy choice without getting worse?
4. Code it — usually a sort plus a single pass.

If step 2 or 3 fails, the answer is probably dynamic programming.

Recap

You now know:

• Greedy means: pick locally best, never reconsider, hope it’s globally optimal.
• Two properties must hold: greedy choice and optimal substructure.
• Coin change is the classic counter-example — small adversarial inputs kill naive greedy.
• The exchange argument is the proof template: optimal’s choice can be swapped for greedy’s without loss.
• Many interval and scheduling problems are greedy after sorting by the right key.

Next steps

Greedy is one paradigm; dynamic programming is its more careful cousin, used when greedy fails. That is a natural next topic — recognising when local choices need global memoisation.

Questions or feedback? Email codeloomdevv@gmail.com.