Greedy

A greedy algorithm commits to the locally best choice at every step and never looks back. That only works when you can show, with an exchange argument, that swapping any optimal solution's choice for the greedy one never makes things worse.

Variant	How it decides	Typical use
Sort, then commit	Sort by a key, take each item once	Pairing, scheduling, matching
Build from the front	Fix the best first piece, then repeat	Smallest number, lexicographic order
Track a feasibility interval	Carry the range of reachable states	Wildcards, running balances

Greedy is a proof pattern, not a data structure. The sort picks the order, and the exchange argument earns you the right to commit. Skip it and greedy is a guess. It falls apart when early choices change the value of later ones, which is where dynamic programming takes over.

Approach	Time	Extra space
Try every order	$O(n!)$ or $O(2^n)$	$O(n)$
Dynamic programming over choices	$O(n^2)$ or $O(n \cdot W)$	$O(n \cdot W)$
Sort, then greedy pass	$O(n \log n)$	$O(1)$

Reach for it when a problem asks you to maximize a count or minimize a cost, each item is accepted or rejected once, and a two-line swap argument backs up the choice.

The problems below start with two sorted-array pairings, move through the median, digit-by-digit construction, deadline scheduling, merging, and a feasibility interval, and end with an order-of-operations exchange.