Question :

Suppose you are asked to automate the prescription fulfillment system for a pharmacy, MailDrugs. When an order comes in, it is given as a sequence of requests, "x1 ml of drug y1," "x2 ml of drug y2," "x3 ml of drug y3," and so on, where x1 < x2 < x3 < ··· < xk.

MailDrugs has a practically unlimited supply of n distinctly sized empty drug bottles, each specified by its capacity in milliliters (such 150 ml or 325 ml).

To process a drug order, as specified above, you need to match each request, "xi ml of drug yi ," with the size of the smallest bottle in the inventory than can hold xi milliliters.

Describe how to process such a drug order of k requests so that it can be fulfilled in O(k log(n/k)) time, assuming the bottle sizes are stored in an array, T, ordered by their capacities in milliliters.