1.13 Greedy Choices

A greedy algorithm builds a solution by making one locally best choice at a time. It does not reconsider earlier choices. This makes greedy algorithms simple and fast, but also easy to get wrong. The main difficulty is proof: you must show that each local choice can be part of some globally optimal solution.

Greedy algorithms work when the problem has structure that makes local progress safe. A choice is safe when there exists an optimal solution that includes it. Once this is proved, the algorithm can commit to the choice and reduce the remaining work to a smaller problem of the same kind.

Problem

You need to decide whether a problem can be solved by repeatedly making the best immediate choice.

Solution

Use a greedy design pattern:

1. Define the candidate choices.
2. Define what "best local choice" means.
3. Prove the choice is safe.
4. Reduce the problem after taking the choice.
5. Repeat until the solution is complete.

The proof is the essential step. A greedy rule without a safety argument is only a heuristic.

Example: Interval Scheduling

Problem:

Given a set of intervals, choose the maximum number of non-overlapping intervals.

Greedy rule:

Always choose the interval with the earliest finishing time.

Algorithm:

interval_scheduling(intervals):
  sort intervals by finish time

  result = []
  current_end = -infinity

  for interval in intervals:
    if interval.start >= current_end:
      add interval to result
      current_end = interval.finish

  return result

The local choice is the interval that finishes earliest among all currently compatible intervals.

Correctness Argument

Let g be the interval with the earliest finishing time. Consider any optimal solution. If that solution already contains g, the greedy choice is safe.

If the optimal solution does not contain g, let o be the first interval in that optimal solution. Since g finishes no later than o, replacing o with g keeps the solution feasible. The number of intervals does not decrease. Therefore there exists an optimal solution that contains g.

After choosing g, the remaining problem is the same problem restricted to intervals that start after g finishes. The greedy rule can be applied again.

This is an exchange argument. It shows that any optimal solution can be transformed into one that agrees with the greedy choice.

Example: Coin Change Warning

Greedy does not always work.

Problem:

Given coin values and an amount, use the fewest coins.

For coin values:

[1, 3, 4]

and amount:

6

The greedy rule “take the largest coin not exceeding the remaining amount” chooses:

4 + 1 + 1

using 3 coins.

The optimal solution is:

3 + 3

using 2 coins.

The local choice of 4 looks best immediately, but it blocks a better global solution. This problem needs additional structure before greedy is valid.

Safe Choice Pattern

A greedy proof usually has this form:

Claim:
  The greedy choice is safe.

Proof:
  Take an optimal solution O.
  If O contains the greedy choice, done.
  Otherwise, modify O by replacing part of it with the greedy choice.
  Show the modified solution is still feasible.
  Show its objective value is no worse.

This argument is common in scheduling, spanning trees, Huffman coding, and some covering problems.

Greedy vs Dynamic Programming

Greedy commits to one choice. Dynamic programming keeps many possible states.

Use greedy when:

A local choice can be proved safe.

Use dynamic programming when:

Several choices may be locally plausible, and the best one depends on future consequences.

For example, interval scheduling by maximum count is greedy. Weighted interval scheduling is usually dynamic programming because a short interval may have low value while a longer interval may have high value.

Common Greedy Signals

Greedy may be promising when the problem has:

These signals do not prove correctness, but they suggest where to look for a proof.

Common Pitfalls

Do not trust a greedy rule because it passes examples. Greedy failures often require small counterexamples but are not obvious.

Do not confuse “largest”, “smallest”, “earliest”, or “cheapest” with “safe.” A local ordering must be connected to the objective.

Do not use greedy when the problem requires exploring incompatible future choices unless a proof eliminates them.

Do not patch a failed greedy algorithm with special cases. If the safe-choice property fails, the strategy is structurally wrong.

Takeaway

A greedy algorithm is valid only when each local choice can be proved safe. The standard proof technique is an exchange argument: transform an optimal solution so that it includes the greedy choice without making it worse.