Greedy Problems

Greedy algorithms make a locally-optimal choice at each step and hope the result is globally optimal. The catch is that this only works for problems with the right structure — a matroid, an exchange argument, or a clear ordering. When the structure is missing, greedy fails silently and you need DP. Recognizing which is which is the interview skill.

The classic greedy interview problems include Maximum Subarray (Kadane's), Jump Game, Gas Station, Hand of Straights, Merge Intervals, and the activity-selection family. The proof of correctness usually comes from an exchange argument: assume an optimal solution exists, then show you can swap any of its choices for the greedy choice without making it worse — therefore the greedy choice is always safe.

The Ratta greedy track covers the foundational set with worked exchange-argument proofs alongside each implementation. Solutions in C++, Java, Python, and Go include both the greedy strategy and a brief note on why it's correct — so you can defend the choice in an interview rather than just submitting code that happens to pass.