InternshipGreedy algorithms
Take the best choice now, and know when that fails.
A greedy algorithm makes the choice that looks best right now and never goes back. When it works it is short and fast, but you must be able to say why a locally best choice never spoils the final answer.
Most meetings in one room
Expected output
3
Always taking the meeting that ends earliest leaves the most time for the rest. That argument is what makes this greedy choice safe.
When greedy fails
Expected output
[20, 10] [4, 1, 1]
For 6 with coins 1, 3 and 4, greedy takes 4 first and needs three coins, but 3 + 3 needs only two. Indian notes happen to suit greedy; for arbitrary coins, use dynamic programming, covered in the next lesson.