- I have a minimum card balance required to visit a club.You should balance equal or more than that.
- Once you visit a club you need to pay some cost. What is the minimum card balance to visit all clubs ?
|Minimum card balance|11|6|5|7|
|Cost Occured | 3|4|2|1|
The answer for this questions is 12. I visit (11,3) → ->(7,1)->->(5,2)->
If i have 500000 such pairs how do i go about solving this problem ? I looking at less than O(N^2) more like O(nlogn) I thought about generating all permutations but it is possible for only less than 10 pairs.
I tried sorting by decreasing order of minimum card balance. (11,3),(7,1),(6,4),(5,2).
- Lets take the minimum cost is 11. Then 11->(11,3)->->(7,1)->->(6,3)->-X not sufficient to buy (5,2). Lets take the minimum cost is 12.Then in the order 12->(11,3)->->(7,1)->->(6,4)-> X
- The order of pairs matter.Even though 12 is a valid solution the order in he visits the club matter.
So i have to try n! ways of visits to club and check the minimum cost one by one which doesn’t solve the problem for 500000 pairs
I also tried sorting by cost occured. 12->(7,1)->->(5,2)->-X Can’t satisfy (11,3).