# 1-D set cover optimisation with connected subsets

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?

• 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 Jan 12 '15 at 16:29
• 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 Jan 12 '15 at 16:32
• I'll write a sketch of the proof. – Marzio De Biasi Jan 12 '15 at 16:38
• :-) Gerhard posted an answer while I was writing mine ... see the correctness notes in the linked lecture. – Marzio De Biasi Jan 12 '15 at 16:48