Greedy Algorithm for Finding Min Set of Intervals that Overlap All Other Intervals

0
votes

I'm learning greedy algorithms and came across a problem that I'm not sure how to tackle. Given a set of intervals (a,b) with start time a and end time b, give a greedy algorithm that returns the minimum amount of intervals that overlap every other interval in the set. So for example if I had:

(1,4) (2,3) (5,8) (6,9) (7,10)

I would return (2,3) and (7,8) since these two intervals cover every interval in the set. What I have right now is this:

  1. Sort the intervals by increasing end time
  2. Push the interval with the smallest end time onto a stack
  3. If an interval (a,b) overlaps the interval on the top of the stack (c,d) (so a is less than d) then if a<=c keep (c,d). Else update the interval on the top of the stack to (a,d)
  4. If an interval (a,b) does not overlap the interval on the top of the stack (c,d) then push (a,b) onto the stack
  5. At the end the stack contains the desired intervals and this should run in O(n) time

My question is: how is this algorithm greedy? I'm struggling with the concepts. So maybe I have this right and maybe I don't, but if I do, I can't figure out what the greedy rule is/should be.

EDIT: A valid point was made below, about which I should have been clearer about. (7,8) works instead of (1,10) (which covers everything) because every time in (7,8) is in (5,8) (6,9) and (7,10). Same with (2,3), every time in there is in (1,4) and (2,3). The goal is to get a set of intervals such that if you looked at all possible times in that set of intervals, each time would be in at least one of the original intervals.

1
algorithmdata-structuresminimumgreedy
How did you come up with (7,8)? It's not one of the original intervals, and to that end, why not pick (1,10) - single interval that covers everything. – Nicko Po
I should have been clearer. The key point is the overlap. So if I chose a time of 4.5, 4.5 is not in any interval (so the (1,10) wouldn't work because not every time in that interval is in each of the intervals). But any time in (7,8) is in (5,8) (6,9) (7,10) so that's why that interval was created. Same with (2,3), any time from 2 to 3 is in (1,4) and (2,3). – codebear
I suggest using the wording "give a greedy algorithm that returns a minimum-size set of intervals X, not necessarily taken from the input set of intervals, such that every interval in the input set has some overlap with at least one interval in X, and no interval in X covers a point in time that is not also covered by some interval in the input". This is complicated, but your current statement is a bit ambiguous, and I couldn't think of anything simpler. Actually a diagram would help clarify things a lot. – j_random_hacker
Also I'm not to clear on the actual question here, but I have a suggestion for your algorithm: In step 3 you shrink the candidate interval, but (if I understand the constraints correctly) this can never improve a solution, and may make it worse! (If we only care about minimising the number of intervals and not, e.g., their total size, then we should always use intervals that are as wide as possible.) – j_random_hacker

1 Answers

0
votes

A greedy algorithm is one that repeatedly chooses the best incremental improvement, even though it might turn out to be sub-optimal in the long run.

Your algorithm doesn't seem greedy to me. A greedy algorithm for this problem would be:

  1. Find the interval that is contained in the largest number of intervals from the input set.
  2. Remove the intervals from the input set that contain it.
  3. Repeat until the input set is empty.

For this example, it would first produce (7,8), because it is contained in 3 input intervals, then reduce the input set to (1,4)(2,3), then produce (2,3)

Note that this algorithm doesn't produce the optimal output for input set: (0,4)(1,2)(1,4)(3,6)(3,7)(5,6)

It produces (3,4) first, since it is covered by 4 input intervals, but the best answer is (1,2)(5,6), which are covered by 3 intervals each