Book: Algorithm Design ( Text book : Kleinberg , J. & Tardos, E. (2014). Algorit
ID: 3702158 • Letter: B
Question
Book: Algorithm Design (Text book :Kleinberg, J. & Tardos, E. (2014). Algorithm Design. Harlow, Essex, U.K.: Pearson. ISBN: 9780321295354)
Book link => http://www.icsd.aegean.gr/kaporisa/index_files/Algorithm_Design.pdf
Consider the following variation on the Interval Scheduling Problem. You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each such job comes with a start time and an end time; if the job is accepted to run on the processor, it must run conl~nuously, every day, for the period between its start and end times. (Note that certain jobs can begin before midnight and end after midnight; this makes for a type of situation different from what we saw in the Interval Scheduling Problem.) Given a list of n such jobs, your goal is to accept as many jobs as possible (regardless of their length), subject to the constraint that the processor can run at most one job at any given point in time. Provide an algorithm to do this with a running time that is polynomial in n. You may assume for simplicity that no two jobs have the same start or end times. Example. Consider the fol!owing four jobs, specified by (start-time, endtime) pairs. (6 P.M., 6 A.M.), (9 P.M., 4 A.M.), (3 A.M., 2 P.M.), (1 P.M., 7 P.M.). The optimal solution would be to pick the two jobs (9 P.M., 4 A.M.) and (1 P.M., 7 P.~1.), which can be scheduled without overlapping.
Explanation / Answer
Let , j1,j2,...jn be the set of n jobs.
As jobs need to run continuously every day, we can place these jobs on a circle (like circle of clock).
Now to schedul jobs optimally as follows:
Preprocessing: Sort all jobs according to their finish time.
1.pick any job j1 and remove all jobs that are overlapped with j1.
2. Now run previous greedy Interval Scheduling, let the optimal number of job is opt1.
3. Similarly for each job ji and find opti.
4. Find maximum among opti, which is our solution.
Above algorithm runs in O(n2) time.
Because preprocessing step to sort jobs takes O(n log n) time.
To process each job to find opti takes O(n) time, so over all jobs take O(n2) time.
So, overall complexity of this algorithm is O(n log n)+O(n2)=O(n2)