Making a decision locally until we reach the constraint. Unlike dynamic programming, where we explore all solutions and recurse into each, in greedy algos we ask a top level question, and immediately answer it.
- No exploration needed, so usually faster than DP.
- Often, coming up with the greedy algorithm is not the hard part. It’s the analysis and proving that takes time… sort of opposite to DP and D&C. This is where exchange arguments come in.
The same intuition about DP problems applies here, because both are usually solving an optimization problem. In particular, when trying to come up with a high-level question, it’s a good idea to prove ourselves wrong for each potential solution. Come up with a counterexample to show that algorithm falls apart.