Greedy algorithms - how to prove they work in interviews

Greedy problems are tricky because the approach seems obvious but proving correctness is hard.

Common greedy problems:

• Activity selection / Meeting rooms
• Jump game
• Gas station
• Task scheduler
• Minimum number of platforms

How to verify greedy works:

1. Greedy stays ahead: Show that at each step, greedy is at least as good as any other choice
2. Exchange argument: Show that swapping any non-greedy choice with greedy doesn't worsen the result

In interviews, I usually say: "I believe greedy works here because [intuition]. Let me verify with examples." Then test with 2-3 cases.

Most interviewers are satisfied with a good intuition + example verification. They rarely ask for formal proof.