Exercise 5 (Greedy algorithms for scheduling) A server has n customers waiting to be served, labeled from 1 to n. The service time for customer i is ti minutes, and is known in advance. Thus, if the customers are served in order of their labels, then customer 1 will wait _l minutes until he/she has been served We wish to minimize the total time that customers are waiting (time spent waiting by customer i) Let I(j) be the label of the jth customer to be served (for example, if 1(1) = 7, then customer 7 is the first customer to be served). Then, the total time T can be written as (i) Give the pseudocode of an algorithm that computes the optimal order in which to process the customers. (Hint: think greedy!) (ii) Show that your algorithm is correct. (Hint: Suppose we swap two customers in the order, say l(j) and l(k). How does total time T change?) (iii) Characterize the run-time of your algorithm