We are given a set of n jobs -the i-th job has a processing time ti > 0 and a we
ID: 3566229 • Letter: W
Question
We are given a set of n jobs -the i-th job has a processing time ti > 0 and a weight wi > 0. We want to order the jobs so as to minimze the weighted sum of completion times, The completion time Ci of job i in a given ordering of the jobs is the sum of the processing times of all jobs up to and including i in the order. For example, for the ordering (2,3,1), the completion time of job 2 is t2, of job 3 is t2 + t3, and of job 1 is t2 + t3 + t1. Design an efficient and correct greedy algorithm for the problem. Argue that the greedy algorithm works correctly whenever n = 2, that is, for all inputs with two jobs.Explanation / Answer
Greedy Solution => we are given n job with weight for any ith job such that 1<= i <= n is wi > 0 and processing time ti > 0 so make an array l such that for every job in this array we have ti / wi ratio. sort this array l such that job with minimum ti / wi comes first. iterate through the each job in the array and perform the job. In this case we have minimum weighted sum of completion time.
Running Time of our greedy solution =>
for each job computing ti / wi is O(1). so for all job this computation is O(n).
sort the array l is O(n log n) [Divide and Conquer]
performing each job and compute its weighted sum of completion time is O(1) so for all job this step is O(n).
so, Time Complexity is O(n) + O(n log n) + O(n)
=> O(n log n)
Proof of Greedy Algorithm when job are 2 => suppose we have 2 jobs each with weight w1 and w2, processing time t1 and t2 respectively.
take a case of: w1 = 100, w2 = 12, t1 = 50, t2 = 4.
we will perform task 2 first becuase ti / wi is low for task2 so weighted sum of completion time is 4*12 + 54 *100 which is optimal as if we do job 1 first we will have weighted sum of completion time => 50*100 + 54*12;
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.