For each 1 <= i <= n job is given by two numbers d(i) and p(i), where d(i) is th

Q: For each 1

Solution: The algorithm is given below: Algorithm: Running time: The above algorithm is sorting the given array based on the penalty and also based on the deadline, which will take n log n time each after that, we are assigning the job in O(n) time so the time complexity will be T(n)= O(n log n). I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

ID: 3718909 • Letter: F

Question

For each 1 <= i <= n job is given by two numbers d(i) and p(i), where d(i) is the deadline and p(i) is the penalty. The length of each job is equal to 1 minute and once the job starts it cannot be stopped until completed. We want to schedule all jobs, but only one job can run at any given time. If job i does not complete on or before its deadline, we will pay its penalty p(i). Design a greedy algorithm to find a schedule such that all jobs are completed and the sum of all penalties is minimized. What is the running time of your algorithm?

Explanation / Answer

Solution:

The algorithm is given below:

Algorithm:

Running time:

The above algorithm is sorting the given array based on the penalty and also based on the deadline, which will take n log n time each

after that, we are assigning the job in O(n) time

so the time complexity will be

T(n)= O(n log n).

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Navigate

For each *data type* learned, write down a literal of that type. Which are primi

For each C code fragment, give the final value of the indicated variable after t

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

For each 1 <= i <= n job is given by two numbers d(i) and p(i), where d(i) is th

Question

Explanation / Answer

Related Questions

Navigate