A car mechanic arrives at his garage in the morning and finds n customers. For each client ci , the engineer calculates the repair time ri of his car. When the engineer starts a repair, he completes it. Repairs can be performed in any order, one at a time. Your goal is to find the order in which repairs are performed with the shortest total waiting time for customers. The wi waiting time of a client ci equals the time it took to repair the cars of customers executed before the customer ci plus the repair time ri . The total T wait time of all customers is equal to the sum of customers' waiting times. For example, consider that there are 3 customers c1, c2, c3 with repair times r1 = 45, r2 = 28, r3 = 35 minutes, respectively. If the tasks are performed in the order of c3, c1, c2, then the customer waiting time is w1 = 35 + 45 = 80, w2 = 35 + 45 + 28 = 108, and w3 = 35. The total waiting time is T = 80 + 108 + 35 = 223. 1) Describe a greedy algorithm to work out problem. Highlight your greedy choice. What is the running time of your algorithm?

2)Formulate and leave in the capacity of greedy choice property. Public, proof, greedy choices in an optimal carefully.

3)Formulate and prove the optimal infrastructure property. That is, prove that the optimal solution to the problem contains the optimal solution of the problem that is created after your greedy choice.​