Compare adjacent contributions F(a,b) and F(b,a). If a transitive relation a≼b guarantees F(a,b)<=F(b,a) for minimization, eliminating every inversion yields a global optimum.
Recognition signals
A solution is fundamentally an ordering or schedule.
The objective decomposes through adjacent order or completion-time effects.
Swapping adjacent objects leaves the rest feasible.
The two local orders can be compared algebraically.
The local preference is transitive or reducible to a sort key.
False friends
Signal
Why it is different
A locally small choice feels right
Without an exchange, cut, or stays-ahead proof, that feeling does not establish optimality.
A decision changes future availability
If swapping alters later feasibility, a pure ordering greedy is usually invalid.
A cyclic comparator
A preference cycle a≺b≺c≺a cannot define a consistent sort order.
Core invariant
The greedy prefix has no local inversion, and at least one global optimum agrees with that entire prefix.
State, transition, and processing order
Item
Definition
State
Objects sorted by the derived key plus accumulated resource, time, or reward during the scan.
Transition
Take the next ordered object; when feasibility filtering remains, accept only in a way separately proved to preserve the prefix invariant.
Frontier / order
The first unprocessed object in greedy order; in the proof, it is the next inversion removed from an arbitrary optimum.
Python skeleton
def greedy_order(items, key, initial_state, feasible, step):
state = initial_state
chosen = []
for item in sorted(items, key=key):
if feasible(state, item):
state = step(state, item)
chosen.append(item)
return chosen, state
Correctness sketch
Take an optimum and locate the first position that disagrees with the greedy order, producing a local inversion b,a.
The exchange inequality permits replacing b,a by a,b without reducing value or feasibility.
A finite number of exchanges yields an optimum in greedy order, so every greedy prefix extends to an optimum.
Complexity
Time
Space
Parameters
Typically O(n log n) sorting plus O(n) scanning
O(n) or sorting-dependent
n is object count; transitivity and feasibility-preserving exchange are prerequisites.
Edge cases
equal keys
overflow in cross products
zero or negative weights
stability and secondary objectives
history-dependent acceptance
Error patterns
Pattern
Why it fails / fix
Guessing a key before doing algebra
Write both adjacent-order costs first, then rearrange their difference into a key.
Proving only the local comparison
The swap must also preserve all other feasibility and be repeatable globally.
Sorting by floating-point ratios
Precision can reverse order; prefer cross products with overflow awareness.
Ignoring ties and the secondary objective
When the main cost ties but stability or lexicographic order matters, specify a second key.
Selection and exclusion rules
Derive the key from F(a,b) versus F(b,a).
Verify that the swap preserves the remaining feasible set.
Check that the preference defines a total order.
If acceptance depends on state, prove it separately or move to DP.