Consider the following variation on the Interval SchedulingProblem. You have a p
ID: 3616623 • Letter: C
Question
Consider the following variation on the Interval SchedulingProblem. You have a processor that can operate 24 hours a day,every day. People submit requests to run daily jobs on theprocessor. Each such job comes with a start time and an end time;if the job is accepted to run on the processor, it must runcontinuously, every day, for the period between its start and endtimes. (Note that certain hobs can begin before midnight and endafter midnight; this makes for a type of situation different fromwhat we saw in the Interval Scheduling Problem).
Given a list of n such jobs, you goal is to accept as many jobs aspossible (regardless of length), subject to the constraint that theprocessor can run at most on job at any given point in time.Provide an algorithm to do this with a running time that ispolynomial in n. You may assume for simplicity that no two jobshave the same start or end times.
Example: Consider the following 4 jobs, specified by (start-time,emd-time) pairs:
(6 P.M., 6 A.M), (9 P.M., 4 A.M.), (3 A.M., 2 P.M.), (1 P.M., 7P.M.).
The optimal solution would be to pick the two jobs (9 P.M., 4A.M.) and (1 P.M., 7 P.M.), which can be scheduled withoutoverlapping.
Analyze the running time complexity and prove the optimality ofthe algorithm you provide. Hint: The Interval Scheduling algorithm(below) may be utilized once we somehow “cut” thearound-the-clock timeline. Theobjective of cutting the timeline is to convert the circulartimeline to a linear timeline as given in the Interval Schedulingproblem of the textbook. Please think how you can do that. One wayis to remove a job and all other jobs overlapping it. Since thereare n jobs, there are n different cases of cutting the circulartimeline. You can then compare the cases to pick an optimalone.
Initially, let R be the set of all requests, and let A beempty
While R is not yet empty
Choose a request i R that has the smallest finishingtime
Add a request i to A
Delete all requests from R that are not compatible with requesti
EndWhile
Return the set A as the set of accepted requests
Explanation / Answer
Optimal solution of interval partioning algorithms greed part isearly first. SCHEDULE(a[1...N]) 1. sort a[1...N] by finish time 2. A<-- a[1] //Scheduledactivity 1 first. 3.prev<--1; 4.for v=2 to N 5. doif(a[v].start>=a[prev].finish) 6. thenA<--AUa[v]; prev<--v Optimal solution of interval partioning algorithms greed part isearly first. SCHEDULE(a[1...N]) 1. sort a[1...N] by finish time 2. A<-- a[1] //Scheduledactivity 1 first. 3.prev<--1; 4.for v=2 to N 5. doif(a[v].start>=a[prev].finish) 6. thenA<--AUa[v]; prev<--v Optimal solution of interval partioning algorithms greed part isearly first. SCHEDULE(a[1...N]) 1. sort a[1...N] by finish time 2. A<-- a[1] //Scheduledactivity 1 first. 3.prev<--1; 4.for v=2 to N 5. doif(a[v].start>=a[prev].finish) 6. thenA<--AUa[v]; prev<--v