We all are familiar with the classic scheduling algorithm where there are n jobs with start time Si and end time Fi for i’th job and we need to find the maximum subset of the jobs such that no two job in the subset overlap with each other. We also know that this can be solved easily using greedy algorithm.
The approach of solving the algorithm is to sort the jobs based on their finish time in non decreasing order and then take jobs starting from the 1st one such that the newly selected job is compatible with the already selected ones.
But in case the time axis is circular, that means if a job can have Fi<Si, what will be the algorithm to solve the job in that case.
Here by circular time axis I mean if the total time length is 0-24 then 24 is equivalent to 0 and a job can start at 23 and end at 5.
I haven’t solved the simple scheudle problem before and also, I can say that my expertise in algorithms is not very great, but, nontheless, I will try to help you! Please forgive me if my idea is wrong.
Obviously, I am assuming that what you mean with circular time is just that you can start a job on, say, day 1 and finish it on day 2, as it makes no sense to assume that Fi < Si, but it is logical to “encode” this new feature with starting and ending a job on different days.
For this, if you have a job with Fi < Si, you can sum 24 to Fi, such that you have times of 00 to 48 and then you can simply apply the same algorithm…
Obviously you would need some maths to get the times correct, but I believe that something on these lines might help you?
@azizul_fahim : Are you looking for the same complexity O(N) which is there for the normal scheduling question . If your circular time is from (0 to t ) where t and 0 means the same thing and each job has scheduling start times and end times as integers . Then you can obviously solve the question in O(t*N) by considering each of the time point as boundary point and apply the original algorithm and take max over all such applications . If time is to considered continuous i.e. start and finish times can be real values then a different approach need to be attempted .
@kuruma : See probably he is not describing his problem in a realistic way but consider a circle and suppose i give you some arc definitions by start angle and end angle ( start angle can be greater than end angle , each angle being between 0 and 360 ) . And I ask you to find the maximum size subsets of arcs in given arcs such that no two selected arc’s intersect . Then that is the problem that @azizul_fahim is trying to communicate .
@azizul_fahim : Can you let me know if your start times and end times can be real . Can you also let me know the expected complexity or is it an open ended question that you have asked . Nice that you came up with it . If its from some source then please mention the source of the problem .
I don’t think that’ll work. Because there might be a job [0,4] and another [22,3]. The two jobs are not compatible. But if we expand the time axis, they will be compatible.
I think I failed to explain properly. Let me try again. For example we have three jobs-[0,4],[5,8],[6,12],[10,2]. Here the optimal solution will be [0,4][5,8]. But the algorithm you proposed will take optimal solution [0,4],[5,8],[10,2]. Because when it expand the time axis it’ll see that job [0,4] and [10,2] are compatible whereas they actually are not.
Remember we want to select maximum subset of jobs such that all the selected jobs are compatible.