Find minimum time required to collect C gifts from A machines given access to B bags?

Question

I have an interview lined up for the next week and am practicing problems for the same. I came across this question, could you please help me with how to solve it?

There are A gift vending machines and you have B pouches to collect the gifts in. Each gift vending machine has unlimited gifts.

Each machine starts dropping the gift at time Si second and keeps dropping a gift every Ii seconds. You can arrange the pouches in any way you like but once they are set below one machine, you cannot move it to another machine. You need to collect a minimum of C gifts in minimum time.

Input

The first line contains the integers A, B, C.

The second line contains integers, Si. ( separated with a space), I goes from 1 to A.

The third line contains integers Ii ( separated with a space), I goes from 1 to A.

Output

An integer which gives the minimum time calculated.

The method I thought was pretty inefficient. I thought that we can have all subsets with their cardinal number equal to B and then choose the one which gives the minimum time.

This approach seems to be brute force, so I'm looking for another alternative approach.

Can any of you please help me with it?

Answer 1

First of all write a function

int max_num_gifts(A,B,t,S[],l[])

which calculates the maximum number of gifts that you can collect with B bags in t time. This can be done in O(A) time: given S[] and l[] the number of gifts the machine A[i] drops is (t-S[i])/l[i]+1. Then get the top B machines which drop the most gifts. See How to find the kth largest element in an unsorted array of length n in O(n)? on how to do the selection in O(n) time.

Then you can just loop through the times t=1,2,... until max_num_gifts >= C. Or better still, you can use a binary search to find such a t: Start with t=1, then check t=2, t=4, t=8 etc until you get too big a number, then binary search for the required t.

The overall time complexity should be O(A* lg(T_min)).