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?
Find minimum number of time points that cross out all intervals
dynamic programming;greedy algorithms;intervals
The solution is as follows. As I have said in the question, we need not check all the time axis explicitly, but we may only traverse the starting and ending points, and if we assume that only starting points can be used to mark the intervals that pass through them, we are right, since the number of intersecting intervals only decreases at ending points.  Since we need as few points selected in the end as possible, the idea is to postpone the selecting of a time point in our final solution as much as possible. Therefore, the suitable algorithm for this problem is greedy. We traverse the starting and ending points in sequential order. When we meet an ending point, we put in the solution the last starting point we met before the current ending point,mark out all the intervals that pass through it, and continue with the remaining intervals. The result is correct because, if we chose some later point, the interval that was about to end would not be crossed out, and if we used an earlier point, we might need some extra points for the rest of the solution than we would have with our algorithm, as we would just increase the number of intervals to be taken care of for the rest of the problem, and for sure that would mean the number of points in the final solution would not be less than that of our algorithm - remember, we want the minimum number of points needed.Deleting the intervals that are marked by a point is easy, if we keep a list of all the intervals that are active at any moment, adding one when we meet its starting point. So when we meet an end point, we put the starting point of the last added in the solution, and clear the list of its intervals.