--- title: "Greedy Choice and the Exchange Argument" description: "A greedy method takes the locally best option and never reconsiders. It can be correct even before a proof is found, but a proof is what shows it is correct, and the usual proof takes any optimal solu" 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-11-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 can be correct even before a proof is found, but a proof is what shows it is correct, 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 one room, the aim is to fit the most activities, with each activity worth the same and no two overlapping. Starting exactly when another ends is not overlapping. The rule is to take the earliest-finishing activity that starts at or after the last pick ends, and repeat with the activities that start at or after it ends. The rule is only safe with a proof. Take any best schedule and swap its first pick for the earliest-finishing one. The swap ends no later, so every later activity in the best schedule still fits, starting at or after it ends, and the count never drops. The rest is the same problem on the activities that start at or after that finish, so the swap argument applies again to the remaining compatible activities. 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. 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. *(drawing: Take the earliest-finishing activity that fits, then repeat with the activities that start at or after it ends.)* **Recap.** For one room, earliest finish among compatible activities wins the most activities when swaps prove it, and coin traps warn you to prove first. ## Practice 8 questions on this page, each with its working shown. ## Optional connections - [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)