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