Its christmas time, and ole Saint Nick has a list of the good children (1, . . . , n ) that he plans to bring presents to. Each kid therefore will receive presents ( p1, . . . , pn). Some kids are very generous, and give Saint Nick some snacks, like cookies; Therefore Ci is to be the number of cookies that Saint Nick will get from kid i. Some of the gifts, like a hot wheels car, are easy to bring and give to the children, while other presents, like a new 2016 BMW, take more effort and more time. Therefore, we let ti be the time it takes Saint Nick to deliver gift i. Assume Saint Nick can bring the presents in any order he chooses, and that it doesnt take Saint Nick any time to ride his sleigh from house to house. Based on the order he picks to deliver each gift, let Di be the time Saint Nick finishes delivery i. Create a greedy algorithm that assists Saint Nick with picking a schedule that minimizes the quantity:

(n over sigma)(i=0 below sigma) Ci D

Basically, in simplier terms, he wants to bring gifts to the high cookie giving kids the fastest (Saint Nick is starving!), but he also wants to consider the time it takes to make each drop-off. Prove the correctness of your algorithm. (Hint: think about a property that is true about an optimal solution.)