Greedy florist wants to sell flowers for more money, and created the following rules:
For a group of k customers to buy n flowers with associated cost [c[0], c[1], …c [n-1]]. First time buyer pay original price, second time buyer will have to pay twice the price, and third time buyer will have to pay third the price…
What’s the algorithm to calculate the minimum cost for the k poor customers?
Link: https://www.hackerrank.com/challenges/greedy-florist/problem
Thinking process:
The strategy is to use the first few times to buy the most expensive flowers, and buy the least expensive flowers the last. To do this, we will need to sort the cost to descending order, and start buying flowers from the start of the list. Let’s look at the code:
Python 3 Solution:
Complexity:
time: 0(nLogn) because we used quick sort
memory: o(1)
Comments and suggestions welcome!