Suppose you are asked to automate the prescription fulfillment system for a pharmacy, MailDrugs. When an order

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.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Algorithm Design And Applications

ISBN: 9781118335918

1st Edition

Authors: Michael T. Goodrich, Roberto Tamassia

Question Posted: