Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let $F$ be a family of sets of consecutive integers in $\{1,…,k\}$ that is closed under taking subintervals, i.e. for any $a≤b≤c≤d$, if $\{a,…,d\} \in F$, then $\{b,…,c\} \in F$ also. Find a minimum number of intervals in $F$ that covers $\{1,…,k\}$.
Is this a known problem? after some trial and error I do have the feeling that greedy solution (picking the longest interval each time) will work here, but will appreciate a proof for that as I do now know how to approach such.
Thanks
Picking the longest interval is not optimal. Consider for example $k=6$, and the (closure obtained by taking subintervals of the) intervals $[1,3], [4,6], [2, 5]$. The longest-interval-first greedy solution will select $3$ intervals, while an optimal solution requires only $2$ intervals.
However the following algorithm is optimal: let $x$ be the smallest uncovered integer. Pick an interval $I=[z, y]$ such that $z \le x \le y$ and $y$ is maximized, add $I$ to your solution and repeat until $\{1, \dots, k\}$ is covered or no $I$ exists (in this case the instance admits no solution).
Feasibility is trivial. You can prove optimality using an exchange argument. Consider an optimal solution $O$ and let $G$ be the above greedy solution. We can assume that $|G \setminus O| > 0$ otherwise we would have $G \subseteq O$, which immediately implies $G=O$. For each interval $\bar{I}$ of $G$ let $z_\bar{I}$ be the integer $z$ that the greedy algorithm was trying to cover when it selected $\bar{I}$. Among all intervals in $G \setminus O$ pick the interval $I$ that minimizes $z_I$. Since $O$ is a feasible solution, there must be some interval $I'$ in $O$ that covers $z$. By the choice of $I$, $O \setminus \{I'\}$ already covers all integers in $1, \dots, k-1$ (otherwise there is an interval $I''$ in $G \setminus O$ such that $z_{I''} < z_I$). Moreover, by the greedy choice of the algorithm, we know that $I$ ends no earlier than $I'$. Therefore $O' = (O \setminus \{ I' \}) \cup \{ I \}$ covers everything that $O$ covers, i.e., it is still a feasible solution. Moreover $|O'| = |O|$, hence $O'$ is actually an optimal solution.
Since $|G \setminus O'| < |G \setminus O|$ (i.e., $G$ and $O'$ share more intervals than $G$ and $O$) we either have $O' = G$ (and we are done) or we can repeat the above argument until we deduce the existence of an optimal solution that matches $G$.
