Identifying when greedy method gives optimum solution

user_14563507 0
Viewed 113

I was looking at this problem on leetcode

https://leetcode.com/problems/minimum-number-of-operations-to-convert-time/description/

The hints tell us to follow a greedy approach where we convert the time difference to minutes and pick the largest possible values

For the given allowed values [1,5,15,60] greedy seems to work for all cases

But let us assume a case where the difference b/w time is 46 minutes and the allowed values are [1,23,40] then as per greedy, the operation would take 7 steps but the minimum possible is 2 ( 23 + 23 )

Why don't we have similar case for the values given the original problem ? how can it be proved that greedy is always the optimal solution in the case of the original problem ? and how can we know, for a given set of allowed values, do we get the optimal solution with greedy or not ?

minimization coin-change greedy algorithm
1 Answers

This problem is very similar to the coin change problem. In general you are very much correct and the greedy solution is not optimal. However is this case the greedy solution is optimal since the "coins" are complete multiplications of each other :

1 * 5 = 5
5 * 3 = 15
15 * 4 = 60

Since this is the case each 60 step can be done by 4 15 steps or 12 5 steps. Therefore the greedy solutions is best in this case.

In the second example you shoed, the "coins" were not a multiplication of each other, making the greedy solution sub-optimal in some cases.

user_183304360
Related