DSA & Implementation · core
Greedy
Local-optimal-as-global proofs.
Mental model
A greedy algorithm always picks the choice that looks best right now. It only gives the right answer when the problem has a structure (an exchange argument) that proves local choices add up correctly. When they do not, greedy quietly returns wrong answers.
How to study Greedy
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use Greedy algorithm (Wikipedia) to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Greedy with Intervals. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Activity selection greedy and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Learn from primary sources
Practice and explain it back
Activity selection greedy
Activities by end time: [1,4],[3,5],[0,6],[5,7],[8,9],[5,9]. Max non-overlapping count?
Expected evidence: 4 activities.
Open the interactive drill →Review prompts
- What is an exchange argument, and why does a greedy algorithm need one?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.