Greedy Algorithms

Discussion of greedy algorithms are strategies

Greedy algorithms are strategies that build solutions step by step, choosing the locally optimal option at each step with the hope of reaching a globally optimal result. They are powerful, simple, and often much faster than dynamic programming or brute force, but they work only when the problem satisfies certain structural properties (such as optimal substructure and the ``greedy-choice property'').

In many classical problems (interval scheduling, minimizing waiting time, activity selection, Huffman coding), greedy algorithms have been proven to produce optimal answers. In competitive programming, the main challenge is recognizing when greediness is correct and what the right greedy criterion is.

Correct greedy solutions usually rely on proofs such as:

• Exchange argument: showing any optimal solution can be rearranged to follow the greedy steps.
• Staying ahead argument: showing that the greedy solution is always at least as good as any other partial solution.

Example 1: Activity Selection Problem

Problem: You are given $n$ activities with start times $s_i$ and finish times $f_i$. Choose the maximum number of non-overlapping activities.