Say we have a set of time intervals, that may intersect. A time point "marks" all of the intervals that are still unfinished at that time point. I wish to find an algorithm so that I can mark all of the intervals using the least amount of time points. E.g. if all of the intervals have not finished at time 6, one point is enough, as point 6 it marks all of the intervals of the problem. Starting and ending time points (
[s(i),e(i)) ) for each interval
i are given. Time points are integer values.
i marks intervals that have started before
i and finish after
i, or intervals that started exactly at
Obviously, I would like something better than plain out trying all possibilities.
I have tried a greedy algorithm, more specifically choosing the point that marks the most intervals at a time (it is easy to see that it is only worth considering points at which an interval starts), removing the intervals it marks and repeating with the remaining intervals. I have found counter-examples showing it does not always give correct results.
The next try would be dynamic programming, which I am breaking my head with right now. However it gets too complex. In the recursive calls I have to make a call for the possibility that the time point checked will be included, and one for the possibility that it will not. However, I must find a way to select a time point anyway, in the case not selecting it will lead to intervals not being marked at all - in that case, I must recognize that before proceeding to the next recursive calls, as I will get false results. It also is a problem how I will keep a record of which intervals proceeded to the recursive call unmarked, without taking too many actions that will increase complexity.
Interval graphs might give me some ideas. If we are talking about interval graphs the problem can be expressed like this: Suppose we have a graph. The nodes are NOT the intervals, but the starting points of each interval. If a starting point of an
interval 1 intersects with an interval (at any of its points)
interval 2, then its node is connected to the starting point node of that
interval 2 with a directed edge. Choosing to mark a node removes the said node and all the nodes it is connected to. What is the least number of markings I must execute in order to erase the whole graph?