### 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