# Introduction to Greedy Algorithms

Authors: Darren Yao, Benjamin Qi

Contributor: Ryan Chou

Problems that can be solved by selecting the choice that seems to be the best at the moment at every step.

## Greedy Algorithms

Some USACO Bronze problems that appear to be ad hoc can actually be solved using
**greedy** algorithms. This idea will be covered in a future
module, but we'll introduce the general mindset in
this section.

Resources | ||||
---|---|---|---|---|

CPH | other examples are outside scope of bronze |

### Warning!

True **"greedy"** problems start to show up in silver, though the greedy mindset
can be very helpful for bronze problems.

From the above:

A

greedyalgorithm constructs a solution to the problem by always making a choice that looks the best at the moment. A greedy algorithm never takes back its choices, but directly constructs the final solution. For this reason, greedy algorithms are usually very efficient.

**Greedy** does not refer to a single algorithm, but rather a way of thinking
that is applied to problems; there's no one way to do greedy algorithms. Hence,
we use a selection of well-known examples to help you understand the greedy
paradigm.

### Example - Mad Scientist

Focus Problem – try your best to solve this problem before continuing!

Try to come up with a greedy algorithm for problem above.

Correct Greedy Algorithm

Solution

Note that not all greedy problems necessarily require mathematical proofs of correctness. It is often sufficent to intuitively convince yourself your algorithm is correct.

### Pro Tip

Sometimes, if the algorithm is easy enough to implement, you don't even need to convince yourself it's correct; just code it and see if it passes. Competitive programmers refer to this as "Proof by AC," or "Proof by Accepted."

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Bronze | Normal | ## Show TagsGreedy | |||

Bronze | Normal | ## Show TagsGreedy | |||

Bronze | Hard | ## Show TagsGreedy | |||

Bronze | Hard | ## Show TagsGreedy | |||

Bronze | Very Hard | ## Show TagsGreedy |

## Quiz

What is a greedy algorithm?

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!