Suppose you are given a set S = {a1, a2, . . . , an} of tasks where p(ai) denotes the processing time of task ai and w(ai) represents the weight (i.e. importance) of task ai . The interpretation of p(ai) is that task ai takes p(ai) units to complete, once it has started execution. You have a single computer on which to run these tasks, and the computer can run only one task at a time. Let ci denote the completion time of task ai ; i.e., the time at which task ai completes processing. Your goal is to minimize the total weighted completion time. That is, you wish to minimize the sum: Xn i=1 w(ai)ci . For example, consider two tasks a1 and a2 where for the first task p(a1) = 1 and w(a1) = 10 and for the second task p(a2) = 3 and w(a2) = 2. Executing the first job followed by the second job would yield a weighted completion time of 101+24 = 18, while executing the second job first would yield 2 3 + 4 10 = 46. Your job is to design an efficient algorithm for determining the schedule of S which minimizes the total weighted completion time. Each task must run non-preemptively (that is, once a task ai is started, it must run continuously for p(ai) time units). You should prove that your algorithm is correct and state its running time