0
$\begingroup$

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 jobs can begin before midnight and end after midnight; this makes for a type of situation different from 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, the number of jobs. You may assume for simplicity that no two jobs have the same start or end times.

I have made an algorithm, but I'm having a hard time proving its correctness. The algorithm is , Select the interval with the least no of intervals overlapping it, remove all the overlapping intervals, and recurse on the remaining intervals.

Here is my proof attempt at proving the correctness of this algorithm:- Let O be an optimal set of intervals which doesn't contain the interval I1, which has the least no of intervals intersecting with it. Consider the set S(I1) that is the set of intervals that intersect with I1. If no elements of S(I1) are in O, then a larger optimal set can be created by adding I1 to O hence, lets consider the case when atleast one Interval , say I2 in S(I1) which is also in O. Now consider O \ {I2} . If none of the elements in O \ {I2} belong to S(I1), then I can exchange I2 with I1 and still have an optimal solution. So lets consider the case when there exists some element in O such that it is in S(I1). Call it I'. as I' lies in O, I' doesn't lie in S(I2). We have |S(I1)| <= |S(I2)| and I' is such that I' lies in S(I1) but not in S(I2). For the inequality to hold , there must exist atleast one interval I'' that is in S(I2) but not in S(I1). This is the point where I'm stuck though, I can't make an exchange argument as I don't know if I'' intersects with other members of O.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Your algorithm is not correct.

Consider intervals [1,7], [8, 14], [15, 21], [22,28], [13,16], [2,9], [3,10], [4,11], [17,23], [18,24], [19, 25].

Your algorithm chooses [13,16] first, as it only overlaps with two other intervals. Then it will only be able to choose two more non-overlapping intervals; one ending before 13, and one starting after 16. The optimal solution chooses 4 intervals, as for example [1,7], [8,14], [15,21], and [22,28].

For an actually correct greedy algorithm it might be easier to think of the non-cyclic case first, so no jobs that go over midnight, and then consider choosing jobs based on their finish time. Once you’re convinced about this go to the cyclic case. If you get stuck in the middle, feel free to make a new question.

$\endgroup$
2
  • $\begingroup$ Ah. Thanks for pointing out that my algorithm is incorrect. For the non-cyclic case I know the correct answer is by considering the earliest deadline first, and we can use that here by fixing an interval but this would be an n^2log n approach, I was wondering if an n log n time greedy algorithm exists for this problem $\endgroup$ Aug 1, 2023 at 21:23
  • $\begingroup$ If you consider your current question correctly answered, feel free to upvote and mark my answer as correct. About whether there is or not a $O(n \lg n)$ algorithm, you should make a separate question. $\endgroup$ Aug 1, 2023 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.