How efficiently can one find small subcovers for integer intervals? This question is inspired by one of my professors giving out

sequential lecture notes that have a significant amount of overlap :-).



What is known about the following problems?

Given a set of integer intervals whose union is an integer interval, find a subset

with the same union that minimizes the number of intervals in the subset.

Given a set of integer intervals whose union is an integer interval, find a subset with the

same union that minimizes the sum of the cardinalities of the intervals in the subset.
Let me restate the first problem:

Problem: Given a set of intervals $\mathcal{S} = \{ I_1, I_2,\ldots,I_n\}$,  minimize $|\mathcal{C}|$, where $ \mathcal{C} =\{ I_{j_1}, I_{j_2},\ldots,I_{j_k}\} \subseteq\mathcal{S} $ and
$ \bigcup_{l=1}^{n}I_l = \bigcup_{m=1}^{k}I_{j_m} $

Define: Graph $G(V,E)$, $V = \{v_1, v_2, \ldots, v_n ,s ,t \}$ where,


Vertex $v_j \in V$ denotes interval $I_j$.
Vertices $v_k, v_l$ have an edge between them if their corresponding intervals $I_k,\; I_l$ overlap.
Source vertex $s$ and $v_j$ have an edge between them if $v_j$'s corresponding interval $I_j$ contains the leftmost point of $\bigcup_{l=1}^{n}I_l $.
Similarly sink vertex $t$ and $v_j$ have an edge between them if $v_j$'s corresponding interval $I_j$ contains the rightmost point of $\bigcup_{l=1}^{n}I_l $.


Answer: The intervals corresponding to the vertices in the 'shortest vertex path' between $s$ and  $t$ gives the minimum set cover!

If I have understood your 2nd question correctly, it is nothing but the weighted 1-dimensional set cover problem.

Remark 1: The intervals $I_j$ considered above might possibly have non-integer end-points.

Remark 2: One can solve this problem using dynamic programming, which I think has "lower" complexity than the shortest path solution.

EDIT-1: For the ease of exposition, I have considered only closed intervals in the above problem.