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 continuously, every day, for the period between its start and end times. (Note that certain hobs 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, you goal is to accept as many jobs as possible (regardless of length), subject to the constraint that the process or can run at most on 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 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 without over lapping.

Analyze the running time complexity and prove the optimality of the algorithm you provide. The Interval Scheduling algorithm(below) may be utilized once we somehow “cut” the around-the-clock timeline. The objective of cutting the timeline is to convert the circular timeline to a linear timeline as given in the Interval Scheduling problem of the textbook. Please think how you can do that. One way is to remove a job and all other jobs overlapping it. Since there are n jobs, there are n different cases of cutting the circular timeline. You can then compare the cases to pick an optimal one.

Initially, let R be the set of all requests, and let A be empty

While R is not yet empty

Choose a request i ∈ R that has the smallest finishing time

Add a request i to A

Delete all requests from R that are not compatible with request End While

Return the set A as the set of accepted requests