Question

Consider the following variant of the Interval Scheduling problem. There are n jobs and each job has a start time si and an end time fi . There is a single machine that can run at most one job at any given time. The jobs are now daily jobs. Once accepted, it must run continuously every day between its start and end times. (Note that a job can start before midnight and end after midnight.)

a) Design an algorithm that accepts as many jobs as possible. Your algorithm should run in time O(n 2 ) and output an optimal schedule (a set of intervals).

b) Prove the correctness of your algorithm and analyze its running time.

Example: Suppose there are 4 jobs, specified by (start-time, end-time) pairs: (9pm, 3am), (6pm, 6am), (3am, 1pm), and (2pm, 7pm). The optimal solution would be to pick 3 jobs (9pm, 3am), (3am, 1pm), and (2pm, 7pm), which can be scheduled without overlapping. (Hint: first enumerate an interval Ij = 1, . . . , n. How could we compute a schedule Oj with maximum size among all valid schedules that contain Ij?)

Answer 1

ANSWER:

Given that,

Consider the following variant of the Interval Scheduling problem.

There are n jobs and each job has a start time si and an end time fi .

There is a single machine that can run at most one job at any given time.

The jobs are now daily jobs

Once accepted, it must run continuously every day between its start and end times.

(Note that a job can start before midnight and end after midnight.)

So,

Let us think od the 24hour duration as circle where each interval is an arc of circle.

If we could some how flatten this circle then the problem just reduces to regular Interval scheduling.

Let j-restricted solution be one that contains the interval I_j.

If a solution contains the interval I_j.

it does not contains any overlapping intervals

let x be a point in Interval I_j.

Remove all intervals intersecting with I_j and choose x to be the point from where we would 'flatten' the circle.

Now we just need to find the maximum number of intervals that can be scheduled excluding the j-th

And its overlapping intervals which can be done in O(n)

Assume,

the intervals are scheduled in increasing finishing time, which they are.

Repeat this procedure for each interval and find the j-restricted solution having maximum number of intervals schedules.

The total runtime in O(n^2)

Since,

There are n j-restricted intervals and finding each j-restricted solution takes O(n) time.