You are given jobs and need to schedule them. Each job is of one time unit duration but provide different profits for the company. Consider the sort as shown below Total Jobs TJ done and the Maximum Profit MP. 1 Sort the jobs based on decreasing order of profit. 2 Create two variables, TJ = 0, MP = 0. 3 Find the maximum deadline among all the jobs. 4 Initialise a set storing all the jobs in decreasing order of profit. 5 Iterate through the jobs and perform the following: i. If the set is empty or the deadline of the current job is less than the last element of the set, ignore the job. ii. Else, apply binary search dividing by deadline < or> i. Find the nearest Slot i, such that i deadline and add the profit. iii. Increment total jobs by 1 and remove the ith element from the set. 6 Return the maximum profit. e.g. 'Item number', complete by, profit [['a', 3, 35], # Job Array arr = ['b', 4, 30], ['c', 4, 25], ['d', 2, 20], ['e', 3, 15], ['f', 1, 12], ['g', 2, 5]] Maximum profit sequence of jobs: dc ab Profit 110 Answer the following questions on this problem (Do not provide code) (a) Do we need to do the initial sort of the jobs array? Why or why not. (b) What will be the efficiency of this algorithm by calculating from the steps of the pseudo code? Explain how you calculated this.
You are given jobs and need to schedule them. Each job is of one time unit duration but provide different profits for the company. Consider the sort as shown below Total Jobs TJ done and the Maximum Profit MP. 1 Sort the jobs based on decreasing order of profit. 2 Create two variables, TJ = 0, MP = 0. 3 Find the maximum deadline among all the jobs. 4 Initialise a set storing all the jobs in decreasing order of profit. 5 Iterate through the jobs and perform the following: i. If the set is empty or the deadline of the current job is less than the last element of the set, ignore the job. ii. Else, apply binary search dividing by deadline < or> i. Find the nearest Slot i, such that i deadline and add the profit. iii. Increment total jobs by 1 and remove the ith element from the set. 6 Return the maximum profit. e.g. 'Item number', complete by, profit [['a', 3, 35], # Job Array arr = ['b', 4, 30], ['c', 4, 25], ['d', 2, 20], ['e', 3, 15], ['f', 1, 12], ['g', 2, 5]] Maximum profit sequence of jobs: dc ab Profit 110 Answer the following questions on this problem (Do not provide code) (a) Do we need to do the initial sort of the jobs array? Why or why not. (b) What will be the efficiency of this algorithm by calculating from the steps of the pseudo code? Explain how you calculated this.
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
![You are given jobs and need to schedule them. Each job is of one time unit duration but provide
different profits for the company. Consider the sort as shown below Total Jobs TJ done and the
Maximum Profit MP.
1 Sort the jobs based on decreasing order of profit.
2 Create two variables, TJ = 0, MP = 0.
3 Find the maximum deadline among all the jobs.
4 Initialise a set storing all the jobs in decreasing order of profit.
5 Iterate through the jobs and perform the following:
i. If the set is empty or the deadline of the current job is less than the last element of the set,
ignore the job.
ii. Else, apply binary search dividing by deadline ≤ or> i. Find the nearest Slot i, such that
i < deadline and add the profit.
iii. Increment total jobs by 1 and remove the ith element from the set.
6 Return the maximum profit.
'Item number', complete by, profit
[['a', 3, 35], # Job Array
['b', 4, 30],
['c', 4, 25],
['d', 2, 20],
['e', 3, 15],
['f', 1, 12],
['g', 2, 5]]
Maximum profit sequence of jobs:
d cab
Profit 110
e.g.
arr =
Answer the following questions on this problem (Do not provide code)
(a) Do we need to do the initial sort of the jobs array? Why or why not.
(b) What will be the efficiency of this algorithm by calculating from the steps of the pseudo code?
Explain how you calculated this.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F5aec3c2c-6648-4536-84ca-a35602e08e38%2F1cc5df6b-f8e1-45a0-a023-22b69db11a2d%2Flq8u4cd_processed.jpeg&w=3840&q=75)
Transcribed Image Text:You are given jobs and need to schedule them. Each job is of one time unit duration but provide
different profits for the company. Consider the sort as shown below Total Jobs TJ done and the
Maximum Profit MP.
1 Sort the jobs based on decreasing order of profit.
2 Create two variables, TJ = 0, MP = 0.
3 Find the maximum deadline among all the jobs.
4 Initialise a set storing all the jobs in decreasing order of profit.
5 Iterate through the jobs and perform the following:
i. If the set is empty or the deadline of the current job is less than the last element of the set,
ignore the job.
ii. Else, apply binary search dividing by deadline ≤ or> i. Find the nearest Slot i, such that
i < deadline and add the profit.
iii. Increment total jobs by 1 and remove the ith element from the set.
6 Return the maximum profit.
'Item number', complete by, profit
[['a', 3, 35], # Job Array
['b', 4, 30],
['c', 4, 25],
['d', 2, 20],
['e', 3, 15],
['f', 1, 12],
['g', 2, 5]]
Maximum profit sequence of jobs:
d cab
Profit 110
e.g.
arr =
Answer the following questions on this problem (Do not provide code)
(a) Do we need to do the initial sort of the jobs array? Why or why not.
(b) What will be the efficiency of this algorithm by calculating from the steps of the pseudo code?
Explain how you calculated this.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY