Consider the following variation on the IntervalScheduling Problem. You have a processor that can operate 24 hoursa 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 solutionwould be to pick the two jobs (9 P.M., 4 A.M.) and (1 P.M., 7P.M.), which can be scheduled without overlapping.
Analyze the runningtime complexity and prove the optimality of the algorithm youprovide. Hint: The Interval Scheduling algorithm may beutilized once we somehow “cut” the around-the-clocktimeline.