1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Jul 3 '21 at 18:54
  • $\begingroup$ You are correct, I've added that since it might be helpful when approaching a proof. tho not sure how yet. $\endgroup$
    – Karambit
    Jul 3 '21 at 18:57
  • 1
    $\begingroup$ stackoverflow.com/q/293168/7217171 $\endgroup$ Jul 3 '21 at 19:23
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks, so basically iteratively picking up the longest interval containing the smallest uncovered integer. Can you please elaborate on the exchange argument? $\endgroup$
    – Karambit
    Jul 3 '21 at 19:54
  • $\begingroup$ Not the longest interval containing the smallest uncovered integer, but the interval that contains the smallest uncovered integer and ends as late as possible (this interval might not be the longest one!!). I have edited my answer with the exchange argument. $\endgroup$
    – Steven
    Jul 3 '21 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.