2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 1. Does a time point $t$ mark all the intervals that contain $t$ (i.e., only intervals that start before $t$ and end after $t$); or does it also mark intervals that start after $t$? $\endgroup$
    – D.W. ♦
    Nov 23, 2016 at 22:19
  • $\begingroup$ 2. What have you tried? What approaches have you considered? What exactly is your question? Obviously it's easy to find some algorithm for this (e.g., try all possibilities). Are you looking for a polynomial-time algorithm? If so, what algorithmic methods have you tried? Have you tried greedy algorithms? dynamic programming? (see our tag wiki) Please show us in the question what you've already tried. 3. Are interval graphs and covering problems on them relevant here? $\endgroup$
    – D.W. ♦
    Nov 23, 2016 at 22:21
  • $\begingroup$ @D.W. Made the edits to the question. $\endgroup$
    – Noob Doob
    Nov 23, 2016 at 23:37
  • $\begingroup$ @D.W. Will do then, thank you a lot :) $\endgroup$
    – Noob Doob
    Nov 23, 2016 at 23:57

2 Answers 2

Reset to default
1
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ But how can one prove the greedy solution is optimum? There is no reason to think that the time points found this way are the minimum number possible just because they're minimal. $\endgroup$
    – Joe Black
    Dec 21, 2018 at 18:42
  • $\begingroup$ @Joe Black Copying from the solution I wrote: "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". This holds true for the first point chosen and, recursively, for the rest. $\endgroup$
    – Noob Doob
    Dec 21, 2018 at 20:48
  • $\begingroup$ @JoeBlack If you leave intervals to take care of for later that could be crossed out in the current step (and we have postponed choosing for as long as possible, that is, until we meet the next ending point), you can at best leave the number of points in the end the same, at worst increase them. $\endgroup$
    – Noob Doob
    Dec 21, 2018 at 20:54
  • $\begingroup$ @JoeBlack Think of it in another way. You want to determine the first such point. Your last "chance" to pick the first point is when you meet the first ending point. So, for that first point, it is only logical to pick the last starting point you met up until then. Recursively, you do that for the "first point" of the new reduced problem, if you delete the intervals that were crossed out in this step. $\endgroup$
    – Noob Doob
    Dec 21, 2018 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.