Greedy algorithms abound in computing.
Well-known examples include Huffman coding, minimum cost spanning trees, and the coin-changing problem; but there are many others.
This pearl adds yet another problem to this collection.
However, as has been said before, greedy algorithms can be tricky things.
The trickiness is not in the algorithm itself, which is usually quite short and easy to understand, but in the proof that it does produce a best possible result.
The mathematical theory of matroids, see [1]}, and its generalisation to greedoids, see [2]}, have been developed to explain why and when many greedy algorithms work, although the theory does not cover all possible cases.
In practice, greedy algorithms are usually verified directly rather than by extracting the underlying matroid or greedoid. [3]} discusses four basic ways in which a greedy algorithm can be proved to work, one of which will be followed with our problem.
