Greedy Algorithms8 sections · 316 units
Open in Course

When Exchange Works Best

Problem characteristics

Exchange arguments work well when:

1.1. There is a natural ordering of choices (first, second, third..)

2.2. You can identify where OPT first differs from G

3.3. Swapping one choice affects only "later" choices, not "earlier" ones

4.4. The swap is valid (does not break constraints) Activity selection fits perfectly: activities are ordered, and replacing an earlier activity with one that ends sooner never conflicts with later choices. When you see a problem with sequential decisions, think exchange argument.