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