Q4 10 Suppose you are a cable guy and are sent out for jobs to complete in a single day. Given job j; each has a start time s; and finish time f;. Your goal is to complete the most number of jobs assigned. The only requirement is you are allowed to start a job late by y minutes, (there is no travel time between jobs). Otherwise, there is no allowed overlap. So I can have a job that goes 1pm-1:37pm and start another one that goes from 1:30pm to 2:30pm PART A Create and analyze code for a greedy algorithm that follows the greedy strategy of choosing the job that starts the latest compatible to currently selected jobs. (HINT you can order jobs in order of decreasing start time) Part B Prove that the greedy strategy of choosing the job that starts the latest is possible in an optimal solution. (Greedy choice property)

icon
Related questions
Question

Please solve the following greedy algorithm problem (show all work) 

solve asap 

Q4
10
Suppose you are a cable guy and are sent out for jobs to complete in a single day. Given
job j; each has a start time s; and finish time f;. Your goal is to complete the most
number of jobs assigned. The only requirement is you are allowed to start a job late by y
minutes, (there is no travel time between jobs). Otherwise, there is no allowed overlap. So
I can have a job that goes 1pm-1:37pm and start another one that goes from 1:30pm to
2:30pm
PART A
Create and analyze code for a greedy algorithm that follows the greedy strategy of
choosing the job that starts the latest compatible to currently selected jobs. (HINT you
can order jobs in order of decreasing start time)
Part B
Prove that the greedy strategy of choosing the job that starts the latest is possible in an
optimal solution. (Greedy choice property)
Transcribed Image Text:Q4 10 Suppose you are a cable guy and are sent out for jobs to complete in a single day. Given job j; each has a start time s; and finish time f;. Your goal is to complete the most number of jobs assigned. The only requirement is you are allowed to start a job late by y minutes, (there is no travel time between jobs). Otherwise, there is no allowed overlap. So I can have a job that goes 1pm-1:37pm and start another one that goes from 1:30pm to 2:30pm PART A Create and analyze code for a greedy algorithm that follows the greedy strategy of choosing the job that starts the latest compatible to currently selected jobs. (HINT you can order jobs in order of decreasing start time) Part B Prove that the greedy strategy of choosing the job that starts the latest is possible in an optimal solution. (Greedy choice property)
Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer