A greedy algorithm makes the choice that looks best right now and never looks back, and when it works, it is one of the simplest and fastest tools in competitive programming.
For students preparing for olympiads like the USA Computing Olympiad (USACO), greedy techniques are a rite of passage. They first appear seriously at the Silver level, where contestants begin learning fundamental problem-solving patterns such as recursive search and greedy strategies, and they continue to surface in Gold and Platinum problems where they are combined with other ideas. Understanding when "grabbing the best option each step" actually produces the best overall answer is a skill that separates careful contestants from lucky ones.
What Makes an Algorithm "Greedy"?
A greedy algorithm builds a solution one piece at a time, always choosing the next piece that gives the most immediate benefit, without reconsidering earlier choices. This is different from dynamic programming, which explores many combinations of choices. Greedy is faster and uses less memory, but it only gives a correct answer when the problem has the right structure.
Two properties make a greedy approach valid:
- The greedy choice property: a locally optimal choice can always be part of some globally optimal solution.
- Optimal substructure: the optimal solution to the whole problem contains optimal solutions to its subproblems.
If both hold, greedy works. If they do not, greedy can produce an answer that looks reasonable but is wrong, which is exactly the trap many beginners fall into during contests.
Classic Problems Worth Knowing
A handful of textbook problems teach almost every greedy pattern you will need in a contest setting:
- Interval scheduling (activity selection): to pick the maximum number of non-overlapping intervals, sort by finishing time and repeatedly take the earliest-ending interval that still fits. Sorting first is the most common greedy setup in USACO Silver.
- Fractional knapsack: sort items by value-to-weight ratio and take the most valuable per unit first, splitting the last item if needed. Note that the 0/1 version, where items cannot be split, requires dynamic programming instead.
- Huffman coding: repeatedly merge the two least-frequent symbols to build an optimal prefix code, a greedy approach used in real data compression.
Pattern to remember: most contest greedy problems start with a sort. Ask yourself "by what key?" — finishing time, ratio, deadline, or size — and the rest of the solution often follows.
Proving Greedy Is Correct
This is the part students skip, and it costs them points. A greedy idea must be justified, not just submitted because the sample case passed. The most reliable tool is the exchange argument.
Assume an optimal solution differs from the greedy one. Find the first place they disagree, then show that swapping in the greedy choice does not make the solution worse. Repeat, and the optimal solution transforms into the greedy solution without losing quality, so greedy must be optimal too.
Other useful techniques include mathematical induction and proof by contradiction. Even a short written argument helps you catch counterexamples before the judge does. When you cannot prove correctness, treat that as a warning sign that greedy may be the wrong tool and dynamic programming or search is needed.
How to Practice
- Solve a problem with brute force first, then look for a greedy shortcut and prove it matches.
- Always try to construct a counterexample to your own greedy idea before coding it.
- Track which sorting key unlocked each problem; over time you will recognize patterns instantly.
USACO runs several contests during the season, each giving competitors a multi-hour window to solve a small set of problems in their division (Bronze, Silver, Gold, or Platinum). Format, eligibility, and timing can change year to year, so check the official USACO information for current details before you register.
Greedy thinking rewards students who reason carefully rather than guess. If your child enjoys this kind of structured problem solving, our competitive programming program at BIAA guides ambitious K-12 students from their first sort-and-select problem all the way to advanced olympiad preparation. Explore BIAA to find the right starting point.