Minimal set of subintervals that 'covers' any subinterval in K subintervals
Let's consider the case $K = 2$. Given an interval $[1,n]$ of length $n$, we can construct the required set as follows:


If $n = 1$, take the entire interval.
Otherwise, let $m = \lfloor n/2 \rfloor$, and take the following intervals:


A solution for $[1,m]$.
A solution for $[m+1,n]$.
All intervals of the form $[i,m]$.
All intervals of the form $[m,j]$.



Denoting by $A(n)$ the number of intervals constructed in this way, we get the recurrence
$$
A(n) = A(\lfloor n/2 \rfloor) + A(\lceil n/2 \rceil) + n,
$$
with initial value $A(1) = 1$. The solution of this recurrence is $A(n) = \Theta(n\log n)$.

Now let us proceed to prove a matching lower bound. Let $\ell_i = 2^i-1$, and let $I$ be the maximum value such that $\ell_i \leq n/2$; note that $I = \Theta(\log n)$. For each $1 \leq i \leq I$, consider the $n/2$ intervals $[1,\ell_i],\ldots,[n/2,n/2+\ell_i-1]$ of length $\ell_i$. Each of these is the union of at most two intervals in $S$, one touching the left endpoint and one the right endpoint (possibly the same one). One of these intervals must have size at least $2^{i-1} &gt; \ell_{i-1}$. In total, this gives a collection of $n/2$ intervals in $S$ of length between $\ell_{i-1}+1$ and $\ell_i$; each such interval is repeated at most twice (since one of its endpoints is a matching endpoint of one of the original $n/2$ intervals). This shows that $S$ must contain at least $n/4$ intervals of size between $\ell_{i-1}+1$ and $\ell_i$, and so $\Omega(nI) = \Omega(n\log n)$ overall.



Here is a better construction for $K=4$. Divide the interval $[1,n]$ into $m=n/\log n$ subintervals $I_1,\ldots,I_m$ of length $\log n$. We construct the required set as follows:


Apply the construction recursively inside each $I_i$.
Every prefix and suffix of each $I_i$, $2n$ intervals in total.
The $K=2$ construction applied to $[1,m]$ and then blown up to $I_1,\ldots,I_m$ by replacing each interval $[i,j]$ to $I_i,\ldots,I_j$.


Let us first show that we can cover each interval $I$ using at most 4 intervals in the set. If $I \subseteq I_i$ for some $i$, then this is clear. Otherwise, suppose that $I \subseteq I_i \cup \cdots \cup I_j$, where $i$ is maximal and $j$ is minimal. So $I$ consists of a suffix of $I_i$, all the intervals $I_{i+1},\ldots,I_{j-1}$ (if any), and a prefix of $I_j$. We can cover the middle part using 2 intervals, and the two ends using 2 more intervals, for a total of 4.

Let us denote by $B(n)$ the number of intervals used in this construction. This quantity satisfies the recurrence
$$
B(n) = \frac{n}{\log n} B(\log n) + O(n).
$$
Opening this up, we get
$$
B(n) = O(n) + \frac{n}{\log n} O(\log n) + \frac{n}{\log n} \frac{\log n}{\log \log n} O(\log \log n) + \cdots,
$$
where the hidden constant is the same for all big O’s. The number of summands is $\log^* n$ (which is the number of $\log$s you have to apply to $n$ to reduce it below some constant), and so
$$
B(n) = O(n\log^* n).
$$
We can repeat this construction once again, for $K=6$, to get the inverse of one level higher on the Ackermann hierarchy. Perhaps in this way we can get a set of $O(n)$ intervals for $K=\omega(1)$ growing extremely slowly (inverse Ackermann); verifying this would require a slightly more careful analysis.