Minimal number of intervals that covers $\{1,...,k\}$

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

• I don't see how $F$ being closed under subintervals is useful here. If you want to cover something, you may as well take $\{a,\dots,d\}$ instead of $\{b,\dots,c\}$ since it covers more elements. Jul 3, 2021 at 18:54
• You are correct, I've added that since it might be helpful when approaching a proof. tho not sure how yet. Jul 3, 2021 at 18:57
• stackoverflow.com/q/293168/7217171 Jul 3, 2021 at 19:23

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$$.