Greedy

Learning Outcome

Reachability, intervals, local choices, and proof-driven greedy patterns.

Item	Detail
Core signal	A known interview family appears and the constraints reward the standard pattern.
Use when	Greedy works only when the local choice can be proven to preserve an optimal future.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Greedy works only when the local choice can be proven to preserve an optimal future.

identify pattern
initialize state/container
for each input unit:
  update state safely
  update answer when invariant is valid
return answer

Take the smallest Greedy example, track the state after every operation, and verify the final answer before coding.

Item	Detail
Expected time	Usually O(n log n), O(V + E), or states times transitions depending on the family.
Expected space	Usually O(n), O(V + E), or number of DP states.

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.