--- title: "Greedy Choice and the Exchange Argument" description: "A greedy method takes the locally best option and never reconsiders. It is right only when a proof says so, and the usual proof takes any optimal solution and swaps its first choice for the greedy one" canonical: https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV- source: https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV-.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Greedy Choice and the Exchange Argument A greedy method takes the locally best option and never reconsiders. It is right only when a proof says so, and the usual proof takes any optimal solution and swaps its first choice for the greedy one without making it worse. Subject: Computing · Area: Algorithms & Data Structures · Ages 19 to 21 Page: https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV- ## Ready when they can - Solve interval scheduling greedily and prove the earliest-finish rule with an exchange - Find a coin system where taking the largest coin first gives the wrong answer - Say what property a problem must have before a greedy rule can be correct ## Lesson: Grabbing the best seat first, with proof A greedy method takes the locally best option and never looks back. For booking rooms, the rule is to take the activity that finishes earliest. That leaves the most room for the rest, and it gives the most activities you can fit. The rule is only safe with a proof. Take any best schedule and swap its first pick for the earliest-finishing one. Nothing breaks, since the swap ends no later, and the count never drops. Repeat the swap and the greedy set matches a best one. **Example.** With coins of 1, 3, and 4, greedy grabs the largest first. For 6 it takes 4, 1, 1: three coins. Yet 3 plus 3 uses two. Largest-first fails here, which proves greedy needs checking every time. **Tip.** Ask two things before trusting a greedy rule. Is the first grab always part of some best answer, and does the rest keep the same shape. If either fails, reach for another method. **Recap.** Earliest finish wins rooms when swaps prove it, and coin traps warn you to prove first. ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Amortised Analysis](https://lightmysky.com/learn/computing/amortised-analysis-mt_1zLrl5RKGr) - [Loop Invariants and Proving an Algorithm Correct](https://lightmysky.com/learn/computing/loop-invariants-and-proving-an-algorithm-correct-mt_fWnstju2ns) ## Opens up - [Randomised Algorithms and the Probabilistic Method](https://lightmysky.com/learn/computing/randomised-algorithms-and-the-probabilistic-method-mt_4ShN_WlT0-) - [Graph Colouring and Planarity](https://lightmysky.com/learn/mathematics/graph-colouring-and-planarity-mt_6xy6UPBppw) - [Living with NP-Hardness: Approximation and Heuristics](https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u) - [Union-Find and Minimum Spanning Trees](https://lightmysky.com/learn/computing/union-find-and-minimum-spanning-trees-mt_zOJei4yCtr)