Find the smallest subset of overlapping intervals

Question

Consider a question to find a minimum dominating set of an interval graph. In the context of interval scheduling, it is converted to the question below:

There are multiple intervals which may or may overlap with each other. Find a minimum subset of the intervals, so that for every interval that is not included in the subset, it will find at least 1 interval in the subset that will overlap with it.

There is an agreed greedy solution available from various sources on the Internet, such as one solution from Cornell: http://www.cs.cornell.edu/Courses/cs4820/2011sp/handouts/samplesolutions.pdf

We work to fill up a set C which makes up the committee (subset of intervals). We use a set M to hold ’covered’ intervals for bookkeeping.

1. Sort the intervals by finish time with earliest finish time first.
2. Take the interval i in S with earliest finish time.
3. Construct set O = {s ∈ S|s intersects i}
4. Take o ∈ O with the latest finish time and add o to C, add all the intervals that intersect with o to M
5. repeat 2-4 until all intervals are covered.

This is similar to a voted up answer provided by interjay in 2012 on SO: Find the smallest set of overlapping jobs

But I have noticed a counterexample that proves the above solution does not produce the minimum subset:

Consider intervals: [0,2], [1,4], [3,10], [5, 6], [7,8], [9, 10].

A minimum subset should have 2 intervals: [3, 10] plus either [0, 2] or [1, 4].

But the above solution will return a subset of 4 intervals: [1,4], [5,6], [7,8] and [9,10]. The longest interval [3,10] was prematurely rejected at step 4.

Is there a better greedy solution than the ones posted above? Thanks!

Deviltry

Answer 1

The algorithm you quoted is incorrect because the set S never changes, so in step 2 the same interval will always be picked and you will enter an infinite loop. If you change step 2 to "Take the interval i in S-M with earliest finish time.", it will be correct.

My answer which you linked is correct however. Both it and the corrected algorithm above will give the set {[1,4], [3,10]} for your example.

The mistake you're making may be that in step 3 above (or step 2 in my linked answer) you're looking only at sets which are in S-M (called A in my answer). But you should look at all intervals that intersect i, even if they are already in M.

Cathey

Thanks for the clarification, interjay! Because of my embarrassingly small number of reputation points, I was not able to comment on your answer from the link directly, so I opened a new question here. I chose your answer here as the correct answer, but was not able to vote up also because of lack of reputation points. lol. Best! – Deviltry