Given a set of jobs {J1, ... , Jn}, each job Ji = < ti, wi > has a required processing time ti and a weight wi. Design an efficient algorithm (pseudo code) to minimize the weighted sum of overall completion times ∑ni=1wiCi, where Ci is the completion time of job i. What is the time complexity of your algorithm? Note: You first need to briefly explain your ideas to solve the problem, e.g. what data structures are used, how the intermediate results are saved, which sorting strategy is used, and why the final results are correct;
Given a set of jobs {J1, ... , Jn}, each job Ji = < ti, wi > has a required processing time ti and a
weight wi. Design an efficient
completion times ∑ni=1wiCi, where Ci is the completion time of job i. What is the time complexity
of your algorithm?
Note: You first need to briefly explain your ideas to solve the problem, e.g. what data structures are
used, how the intermediate results are saved, which sorting strategy is used, and why the final
results are correct;
A common approach to solve this problem is to use a greedy algorithm. The idea is to sort the jobs in decreasing order of the ratio wi/ti, and then schedule them one by one. This way, we ensure that the job with the highest weight/time ratio is completed as soon as possible, which in turn minimizes the weighted sum of overall completion times.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
