# Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

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.

• 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. Commented Aug 1, 2023 at 22:00