I have been studying a problem in my work and I have reduced my problem to likewise Activity Selection problem. It is a problem that I know and I am familiar with the greedy solution.

However, in my problem, start time of my activities are able to shift(forward or backward) in some extend while the duration still same. Let say 15 minutes. I assume that this might give a better optimization than a traditional problem.

On the other hand, I am not sure how to solve this problem. One idea comes to my mind is like that:

 - Create 30 more activity from -15 min to +15 min for each single original activity which they forms a set of 31
 - Run the original greedy search
 - Chose only one of each set of 31 item.

In this sense, there comes another issue, how to chose as in the 3rd step of the algorithm.

I would like to get your comments about my approach. Is it efficient? Would there be any better solution?

Thanks in advance

  • 1
    $\begingroup$ Comment: if you can assume that each activity takes at least 31 minutes, then your approach will choose at most 1 of the copies of an activity. More generally, if activity $A_i$ can be shifted forward or backward by $t_i$ minute, then the copies $A_i-t_i, A_i-(t_i-1), \ldots, A_i-1, A_i, A_i+1, \ldots, A_i+t_i$ are all overlapping if the length of $A_i$ is at least $2t_i+1$ $\endgroup$ – Matthew C Nov 7 '19 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.