For the upcoming bake sale you are planning to bake n differ

For the upcoming bake sale, you are planning to bake n different recipes, labeled r1, r2, . . . rn. Recipe ri requires pi minutes of preparation time and bi minutes of baking time. Fortunately, you have access to a test kitchen with n ovens, so all of recipes can bake simultaneously once they are prepared. However, there is only one of you, so you need to decide in which order to complete the preparation of each recipe.

For example: as soon as you complete preparing the first recipe, you can put it in the oven to bake and immediately begin preparing the second recipe. When you complete the second recipe, you can put it in the oven to bake whether or not the first recipe is done baking; and so on.

Lets say that a schedule is an ordering for preparation of the recipes, and the completion time of the schedule is the earliest time at which all recipes are done baking. This is an important quantity to minimize, because the bake sale is coming up soon!

Give a polynomial-time algorithm that finds a schedule with as small a completion time as possible

Solution

Since the number of ovens available is n this means that all the recipe can be backed in bi time simultaneously.

So total time taken to bake the recipe will be = pi*n+bi with this algorithm. This means that the given algorithm will take O(n) time to compute.

Suppose if we take the scenario which is given in the question then the time taken in baking the recipe would have been = n*pi+ bi.

Since all n recipe you have o prepare you cannot do anything about it, but when you start to bake your recipe as soon as you prepare them then when you put last recipe it will take bi time to be baked. It means time taken is same as the given algorithm, so why taking overhead of putting on recipe at a time to increase overhead.