Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 63 ยท Search and Greedy Thinking

Greedy Algorithms and How to Trust Them

Learn to trust a greedy solution before you submit: exchange arguments, stays-ahead proofs, and a brute-force counterexample hunt, with interval scheduling and lateness.

A greedy solution makes the locally best choice at every step and never looks back. When it works, it is short, fast and elegant. When it fails, it fails quietly: it passes the samples, passes half of the tests, and then earns a Wrong Answer. The hard part of greedy problems is not writing the code. It is knowing whether to believe the idea.

This lesson gives you three tools for that. You will learn the exchange argument and the stays-ahead argument, which are the two standard proof styles, and a practical habit that works even when you cannot find a proof: hunt for counterexamples with a brute force. The general theory, and how greedy compares with dynamic programming, is in Greedy Algorithms and Greedy vs Dynamic Programming; here we focus on contest use.

The exchange argument

The idea: take any optimal solution that differs from the greedy one, and show you can swap pieces of it toward the greedy choice without making it worse. Repeating the swap turns the optimal solution into the greedy solution, so greedy is optimal too.

Take interval scheduling: choose as many non-overlapping intervals as possible. The greedy rule is "always take the interval that finishes earliest among those that fit". Suppose an optimal schedule starts with some interval X, but the greedy pick G finishes no later than X. Replace X with G. Everything after X still fits, because G ends at or before X ends. The schedule is as large as before and now agrees with greedy on its first interval. Repeat for the rest.

flowchart TB
    A["Optimal solution O differs from greedy G"] --> B["Find first position where they differ"]
    B --> C["Swap O's choice for G's choice"]
    C --> D["Show the result is still valid and no worse"]
    D --> E["O now agrees with G for one more step"]
    E --> B

Each swap makes the optimal solution agree with greedy for one more step.

Not every plausible rule survives. "Earliest start" fails because one long early interval can block many short ones, and "shortest first" fails because a short interval in the middle can block two others. The next TryIt tests all three rules against an exhaustive search on random small inputs and prints the first counterexample it finds for each.

Python Which interval rule is right? Test them

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed counterexamples are small, and that is typical: wrong greedy rules are usually broken by a tiny input. This is why a brute force on inputs of size 5 to 8 is so effective.

The stays-ahead argument

The second proof style compares greedy with any other solution after each step and shows greedy is never behind. Interval scheduling also has a stays-ahead proof: after choosing k intervals, the greedy schedule finishes at the earliest possible time of any schedule with k intervals, so it can always fit one more whenever another schedule can.

A cleaner example is the minimum-lateness problem. You have jobs, each with a duration and a deadline, one machine, and no gaps. The lateness of a job is how many time units it finishes after its deadline (zero if on time). You want to minimize the maximum lateness. Sorting by earliest deadline first is optimal: if two adjacent jobs are in the wrong order (a later deadline before an earlier one), swapping them cannot increase the maximum lateness. That is an exchange argument on neighbors, and it is the same pattern as bubble sort.

Python Earliest deadline first versus all orders

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both proof styles are really the same thought: "any solution can be rearranged toward the greedy one for free." If you cannot finish that sentence, you do not yet have a proof, and you should test.

Counterexample hunting for coin-like problems

Some famous greedy rules depend on the input data, not only on the idea. Taking the largest coin first is optimal for coins 1, 5, 10, 25 but not for 1, 3, 4. You can detect this quickly: compute the true answer with dynamic programming for every small amount and compare.

A related stays-ahead example is the "jump game": each cell tells how far you can jump, and you want to know whether the last cell is reachable. Tracking the farthest reachable index while scanning is greedy and correct, because the farthest reach is always at least as good as any other path's reach at the same step.

Python Hunting counterexamples for coin systems

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A contest checklist for greedy

  1. Write the rule in one sentence. If you need "usually" or "except when", it is probably wrong.
  2. Try to break it first. Draw three tiny inputs where the rule might fail: ties, a very long item, a very short item.
  3. Look for an order. Many greedy problems are "sort by key, then scan". Think about which key makes adjacent swaps harmless.
  4. Write a brute force for n at most 8 and compare on random cases. This costs about five minutes and catches most wrong rules; see Stress Testing with a Brute Force.
  5. If it keeps failing, consider dynamic programming: when the best choice depends on what comes later, you need to try several choices, and DP Problem Patterns is the next tool.

Classic contest greedy problems that follow these patterns include scheduling activities, assigning the smallest sufficient resource to each request, merging smallest items first with a heap, and choosing a sort key for pairs (covered in the next lesson).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does an exchange argument prove?

    You swap a piece of an optimal solution for greedy's choice and show validity and quality are kept. Repeating this turns the optimal solution into the greedy one.
  2. 2. Which greedy rule is correct for choosing the maximum number of non-overlapping intervals?

    Finishing earliest leaves the most room for later intervals. The other two rules have tiny counterexamples.
  3. 3. Coins are 1, 3 and 4 and the amount is 6. What does 'largest coin first' give compared with the optimum?

    Greedy takes 4 + 1 + 1 for 3 coins, but 3 + 3 uses only 2. This coin system is not canonical.
  4. 4. What is the most reliable way to test a greedy idea during a contest?

    Wrong greedy rules are usually broken by very small inputs, so an exhaustive brute force on sizes up to about 8 finds them quickly.

Summary

  • A greedy solution is only as good as its justification; samples are not evidence.
  • Exchange argument: swap an optimal solution's choice for greedy's choice and show it is no worse.
  • Stays-ahead argument: show that after each step greedy is at least as far along as any other solution.
  • Earliest finish time solves interval scheduling; earliest deadline first minimizes maximum lateness.
  • Whether greedy works can depend on the data (coin systems), so test it with a brute force and a counterexample hunt.
  • If every simple rule fails, the problem usually needs dynamic programming.

Next: Sorting, Events and Sweeps