<p>The leftmost point must be covered by <em>some</em> interval. There is no harm in picking the <em>longest</em> interval that covers the leftmost point. Then iterate (after removing the interval and all covered points from the instance).</p>

<p>This is the well-known greedy algorithm for the "Interval Point Cover" problem;
see for instance the <a href="http://www.cse.yorku.ca/~andy/courses/3101/lecture-notes/IntervalCover.html" rel="nofollow">course page by Andranik Mirzaian</a> for a full analysis.</p>

CC BY-SA 3.0
2015-01-12T16:40:03.423Z
2015-01-12T16:40:03.423Z
Gamow
<p>Given a 1-D universe $U$ (e.g. $\mathbb{Z}$) and a set-of-sets $\pmb{S}$, where each element of $\pmb{S}$ is a closed, connected subset of $U$ (e.g. $[a .. b]$ given $ a,b\in\mathbb{Z}$) and $\bigcup\pmb{S}=U$, what is the quickest way to find $\pmb{S}^*\subseteq \pmb{S}$ with the smallest cardinality such that $\bigcup \pmb{S}^* = U$?</p>

<p>In other words, is there a fast 1-D set cover optimisation algorithm given that the sets you're working from are closed-connected?</p>

<p>It seems to me that the naive greedy set cover will in fact be optimal here, but I'm not expert enough to prove it. Can anyone think of a counter-example?</p>

CC BY-SA 3.0
2015-01-12T16:29:01.337Z
You can use a greedy algorithm starting from the lower element and picking the largest interval that covers the first lowest uncovered element. It's not hard to prove that it is optimal.
Marzio De Biasi
CC BY-SA 3.0
2015-01-12T16:32:48.150Z
That was the first solution we thought of. Do you have a reference to a proof that it's optimal? This isn't my area of expertise.
John_C
CC BY-SA 3.0
2015-01-12T16:38:14.143Z
I'll write a sketch of the proof.
Marzio De Biasi
CC BY-SA 3.0
2015-01-12T16:48:38.153Z
:-) Gerhard posted an answer while I was writing mine ... see the correctness notes in the linked lecture.
Marzio De Biasi
<set-cover>
1-D set cover optimisation with connected subsets
John_C
# 1-D set cover optimisation with connected subsets

(Asked by: username_0 on 2015-01-12)

Given a 1-D universe $U$ (e.g. $\mathbb{Z}$) and a set-of-sets $\pmb{S}$, where each element of $\pmb{S}$ is a closed, connected subset of $U$ (e.g. $[a .. b]$ given $ a,b\in\mathbb{Z}$) and $\bigcup\pmb{S}=U$, what is the quickest way to find $\pmb{S}^\*\subseteq \pmb{S}$ with the smallest cardinality such that $\bigcup \pmb{S}^\* = U$?

In other words, is there a fast 1-D set cover optimisation algorithm given that the sets you're working from are closed-connected?

It seems to me that the naive greedy set cover will in fact be optimal here, but I'm not expert enough to prove it. Can anyone think of a counter-example?

**Tags:** set-cover

> **Comments:**
> **username_1**: You can use a greedy algorithm starting from the lower element and picking the largest interval that covers the first lowest uncovered element. It's not hard to prove that it is optimal.  
> **username_0**: That was the first solution we thought of. Do you have a reference to a proof that it's optimal? This isn't my area of expertise.  
> **username_1**: I'll write a sketch of the proof.  
> **username_1**: :-) Gerhard posted an answer while I was writing mine ... see the correctness notes in the linked lecture.  

---

## 1 answers

### Answer by username_2 on 2015-01-12. Score: 1 | Accepted answer

The leftmost point must be covered by *some* interval. There is no harm in picking the *longest* interval that covers the leftmost point. Then iterate (after removing the interval and all covered points from the instance).

This is the well-known greedy algorithm for the "Interval Point Cover" problem;
see for instance the [course page by Andranik Mirzaian](http://www.cse.yorku.ca/~andy/courses/3101/lecture-notes/IntervalCover.html) for a full analysis.


---

