You now understand the greedy approach:
Make locally optimal choices
Never reconsider past decisions
Requires greedy choice property and optimal substructure
Works when local optimum leads to global optimum. But how do you know greedy is correct? In the next section, I will show you proof techniques: exchange arguments and the "stays ahead" method. These tools let you verify greedy strategies with confidence. The proof techniques in the next section let you verify correctness without submitting and waiting for test failures. Learn them well.