Given a set SS = {tt1,tt2, … ,ttnn} of tasks, where ttii requires ppii units of processing time to finish once it has started. There is only one computer to run these tasks one at a time. Let ccii be the completion time of task ttii The goal is to minimize the average completion time 1nn ∑ ccii nnii=1 . For example, two tasks tt1 and tt2 have processing times pp1= 3 and pp2 = 5 respectively; running tt1first results in the average completion time (3 + 8)/2 = 5.5, while running tt2 first results in the average completion time (5 + 8)/2 = 6.5. (1) Describe the greedy choice property and the optimal substructure in this problem,
(2) Design a greedy algorithm to solve this problem,
(3) Analyze the complexity of your algorithm.