- 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) → [9]->(7,1)->[8]->(5,2)->[6]
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)->[8]->(7,1)->[7]->(6,3)->[4]-X not sufficient to buy (5,2). Lets take the minimum cost is 12.Then in the order 12->(11,3)->[9]->(7,1)->[8]->(6,4)->[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)->[11]->(5,2)->[9]-X Can’t satisfy (11,3).