Groups
Category
Greedy algorithm correctness is usually proved with patterns like exchange argument, stays-ahead, structural arguments, cut-and-paste, and contradiction.
The exchange argument proves a greedy algorithm is optimal by swapping out-of-order choices in any supposed optimal solution until it matches the greedy one without making it worse.