You have a list of jobs that need to be scheduled. For each job, you know when it should start and when it should end. You need to come up with an algorithm to schedule the maximum number of jobs possible.
Approach using greedy algorithm:
Template for Greedy Algorithm
Process jobs in some order. Add next job to the result if it is compatible with the jobs already in the result.
Key question: in what order should we process the jobs?
Earliest start time Increasing order of start time s(i).
Earliest Fnish time Increasing order of Finish time f(i).
Shortest interval Increasing order of length f(i) - s(i).
Fewest conicts Increasing order of the number of conflicting jobs. How fastcan you compute the number of conicting jobs for each job?
Greedy ideas that do not work:
|___| |______| |______| |______|
|______________________________________|
______________________________________________________________________>
It does not work if we select the interval which starts earliest.
|________________| |_______________|
|_________|
______________________________________________________________________>
It does not work if we select the shortest intervals.
|___| |______| |______| |______|
|____| |_____| |_____|
|____| |_____|
|____| |_____|
______________________________________________________________________>
It does not work to select the intervals with fewest conflicts.
Schedule jobs in order of earliest finish time (EFT)
initially let R be the set of all requests, and let A be the empty set.
While R is not empty
choose a request i belonging to R that has the smallest finishing time.
Add request i to A.
Delete all requests from R that are not compatible with request i.
Done.
input all the intervals.
sort them by the end times.
pick the first one and remove all the intervals which are conflicting with it.
now pick the next one, and again remove all the intervals which are conflicting with it.
repeat till there are no intervals left.
No comments:
Post a Comment