Greedy Algorithms : Need help with the problem below! Problem: Scheduling jobs w
ID: 3717753 • Letter: G
Question
Greedy Algorithms: Need help with the problem below!
Problem: Scheduling jobs with penalties
For each 1 <= i <= n job ji is given by two numbers di and pi, where di is the deadline and pi 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 pi.
a) Design a greedy algorithm to find a schedule such that all jobs are completed and the sum of all penalties is minimized.
**NOTE: Pseudo-code is required for this step!
b) What is the running time of your algorithm?
**NOTE: the answer to part (b) should be theta(n^2)
Explanation / Answer
Time complexity You have 2 loops taking O(N) time each and one sorting function taking O(N * logN). Therefore, the overall time complexity is O(2 * N + N * logN) = O(N * logN).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.