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 rather than a data structure. Usually a sort picks the order you visit items, and an exchange argument shows why committing right away is safe. Without that swap check, a greedy rule is just a guess. Whenever an early choice can hurt a later one in ways you cannot trade back, you need dynamic programming instead.

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 simple swap argument backs up the local choice.

The problems below start with sorted pairings and median alignment, move through digit-by-digit construction, deadline scheduling, and tracking a feasible balance range, and end with choosing which substring pair to remove first.