Consider the following variation on the Interval Scheduling Problem. You have a
ID: 3666277 • Letter: C
Question
Consider the following variation on the Interval Scheduling Problem. You have a processor that can operate 24 hours a day, even' day. People submit requests to run dally 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 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 pi. You may assume for simplicity that no two jobs have the same start or end times. Example. Consider the following four Jobs, specified by (start-limp., end-time) pairs. The optimal solution would be to pick the two Jobs (9 p.m., 4 a.M) and (1 p.m.. 7 P-M.), which can be scheduled without overlapping.Explanation / Answer
This is like the interval scheduling problem discussed in class except that jobs are periodic. One way of thinking about this is that time is not like an interval, but is a circle (think of it as the circle in a clock). Now, each job corresponds to an interval in this circle. Now, suppose we knew the job which are being done at midnight – call this j. Then, we could remove all jobs overlapping with j, and solve the remaining problem. The remaining problem looks like the interval scheduling problem done in class (and so can be solved using a greedy algorithm). However, we do not know the job j. One way out is to try out all possibilities for such a job: for each job which contains the mid-night time, we select it and solve the resulting interval scheduling problem. Finally, we pick the best such solution.