30

Problem 2. (10 points) You are given a list of n jobs 31, 32, ..., in each with a time t() to perform a job and a weight w(j). We want to order the jobs as jo(1); Jo(2) --- Jo(n) in such a way that the quantity TI (uljov) )) ((id(i)) (() k=1 is minimized. In other words, we want to minimize the weighted sum of the time each job has to wait before being executed. Give an efficient greedy algorithm for this problem, analyze the complexity, and prove its optimality