Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Lemonade Change

Making change greedily

You sell lemonade for 5each.Customerspaywith5 each. Customers pay with 5, 10,or10, or 20 bills, and you must give correct change. You start with no money. Return true if you can serve all customers.

Example: bills = [5, 5, 5, 10, 20]. Answer: true. First three give 5each(youhave5 each (you have 15). Fourth pays 10,yougive10, you give 5 back (10leftasone10 left as one 10). Fifth pays 20,yougive20, you give 15 back ($0 left). All served!

What is the greedy choice when giving change? The greedy choice: when you need 15back,preferone15 back, prefer one 10 plus one 5overthree5 over three 5 bills. Why? The $5 is more versatile for future customers.