Greedy Algorithm Template

Sort or traverse in a safe order, maintain invariants, accumulate answer.

Try this in Python

xs = [5, 2, 8]
ans = 0
for x in sorted(xs):
    ans += x
print(ans)

Key takeaways

• Greedy on trees often picks leaves or farthest useful node.
• For graphs, Dijkstra is a greedy proof.
• Document why your ordering is safe.