Find minimum number of time points that cross out all intervals 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.  

The point i marks intervals that have started before i and finish after i, or intervals that started exactly at i.  

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?
Hint: 


   Try some more greedy algorithms; keep trying, and don't give up yet.  You might try solving some small examples by hand, to get some intuition for what is going on, and see what strategies you end up developing.  The way to look for a greedy algorithm is to try all greedy strategies you can think of -- it's not enough to just try one particular strategy and if that doesn't work give up on the entire paradigm of greedy algorithms.


This looks like a nice learning exercise, so keep at it.  You can do it.  (We're glad to help you understand concepts but just solving this exercise for you probably won't help with that.)