Algorithm solution

You are in charge of scheduling private skiing lessons. There are n customers who all arrived simultaneously, but there is only one instructor who can take only one customer at a time. You know that customer i will take time ti to complete the lesson. For instance, if you schedule customer 5 first, followed by customer 3, and followed by customer 7, then customer 7 will get to start the lesson at time t5 + t3. Your input is an array T that contains t1, . . . , tn. Your output should be a permutation of values 1, . . . , n representing the order in which customers should go (in the above example, the permutation would begin with values 5, 3, 7). (a) You want to produce a schedule that minimizes the average wait time per customer until the lesson starts. Design an efficient algorithm to do so, prove that it’s correct, and analyze its running time. (b) You now realize that some customers are more precious to you than others. Each customer is now given a value vi. Instead of minimizing the average wait time, you now want to minimize the weighted average wait time, where each customer’s wait time is weighted by vi (for example, if t1 = 4, t2 = 2, t3 = 5, v1 = 10,v2 = 20,v3 = 15, then the weighted average wait time of the schedule (t1,t2,t3) is (0 · 10 + 4 · 20 + 6 · 15)/(10 + 20 + 15). Design an efficient algorithm to do so, prove that it’s correct, and analyze its running time. Hint: this is a greedy algorithms problem, but it’s hard to figure out what the correct greedy choice is. Think about the ratio of customer time to customer value.