For half-open I=[s,e), selection variants often sort by e and accept when s>=last_end. Merge and cover variants usually sort by s and maintain a farthest end. The objective determines both endpoint semantics and sort key.
Recognition signals
Objects are one-dimensional start/end intervals.
The objective concerns compatibility, conflict removal, coverage, merging, or resource count.
After sorting, a small boundary summarizes the processed prefix.
An earlier finish leaves at least as much room for future choices.
An exchange argument can justify replacing a local choice.
False friends
Signal
Why it is different
Weighted interval selection
Earliest finish need not maximize total value; use DP with predecessor lookup.
An arbitrary conflict graph
When conflict is not interval intersection, one endpoint cannot summarize future feasibility.
Dynamic insertion and deletion
A one-time sorted scan does not maintain an online set; use an ordered or range structure.
Core invariant
Among solutions with the same number of selections from the processed prefix, the greedy one has a finish boundary no later than any replacement and therefore leaves maximal future room.
State, transition, and processing order
Item
Definition
State
Sorted intervals, last_end, and the answer; coverage variants may instead track current_end and farthest.
Transition
Accept a compatible interval and update the boundary. On conflict, retain the alternative that constrains the future least, usually the earlier finish.
Frontier / order
The endpoint order dictated by the proof: typically finish order for selection and start order for merge or coverage.
Python skeleton
def max_compatible(intervals):
# Half-open intervals [start, end).
ordered = sorted(intervals, key=lambda p: (p[1], p[0]))
chosen = []
last_end = float('-inf')
for start, end in ordered:
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
Correctness sketch
Let g be the feasible interval with earliest finish and o the first interval of an optimum; end(g)<=end(o).
Replacing o with g preserves every later feasible interval and the selected count.
After removing the prefix covered by g, the remainder is the same problem; repeated exchanges produce the greedy optimum.
Complexity
Time
Space
Parameters
O(n log n), with an O(n) scan
O(n) for copied order/output; potentially less in place
n is interval count; endpoint closure changes compatibility.
Edge cases
no intervals
zero-length intervals
whether touching endpoints conflict
equal finishes
start greater than end
mixing closed and half-open intervals
Error patterns
Pattern
Why it fails / fix
Guessing the sort key
Compatibility selection and merging need different orders; derive the key from the invariant.
Off-by-one endpoint logic
Half-open intervals allow >=; closed intervals may require >. State the model first.
Applying an unweighted proof to values
The exchange preserves cardinality, not unequal rewards.
Keeping the later finish
That consumes more future space and reverses the selection invariant.
Selection and exclusion rules
Classify the task as selection, merge, or coverage before choosing an order.