Links
AUTHOR
Name: Vishal Khopkar
DIFFICULTY:
MEDIUM
PREREQUISITES:
Greedy
PROBLEM:
We are given a list of n railway stations with their footfall and cost of wifi and wish to select k stations out of them such that the ratio of their total usage to the cost should be minimum.
QUICK EXPLANATION:
The problem can be solved by a greedy approach with a complexity of O(nk)
EXPLANATION:
A brute force approach would be to generate all combinations by selecting k stations out on n in nCk ways and then finding which combination gives you the maximum ratio. However, this would go out of the time limit. Hence, a shorter solution has been proposed by Mr. Rahul Sharma