Finding the minimum subset of intervals covering the whole set

Question

Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers and $a < b$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any value within the range of any pair in $A$, the value is also within the range of any pair in $B$.

I am currently considering setting $B$ equal to $A$ and, for each pair in $B$, if removing the pair still upholds the property of $B$ described above, remove it. However, I feel this algorithm is too inefficient. Is there a more efficient algorithm?

Answer 1

Here's an $O(n\log n)$ algorithm, which is optimal in the algebraic decision tree model by an easy reduction from element distinctness (map each element $x$ to the interval $(x,x+\epsilon)$). We follow Kaveh's outline. Stage 1 runs in $O(n\log n)$ time, so we focus on Stage 2.

Let $I$ be the set of intervals in $C = (a,b)$. Define the intervals $l=(a,a+\epsilon)$ and $r=(b-\epsilon,b)$, and consider the interval graph over $I \cup \{l,r\}$ (two vertices are connected if the corresponding intervals intersect). I claim that every path from $l$ to $r$ corresponds to a cover of $C$, and vice versa.

First, consider a path $P$ from $l$ to $r$. Suppose that $P$ doesn't cover some point $x \in C$. We prove by induction that all the intervals in $P$ are to the left of $x$, which leads to a contradiction since $r$ is to the right of $x$. Clearly $l$ is to the left of $x$. Suppose some $p \in P$ is to the the left of $x$, and let $p'$ be the next interval on the path. If $p'$ were to the right of $x$, then since $p$ and $p'$ intersect, $x$ would have been covered. So $p'$ must also be to the left of $x$.

For the other direction, order the intervals in a cover of $C$ in increasing order of their starting point. If two consecutive intervals $(a,b),(c,d)$ do not intersect then the point $x = (b+c)/2$ is not covered. Similarly, the first interval must intersect $l$. While it is not generally true that the last interval must intersect $r$, one of the intervals must, and if we cut the cover short at the first such interval, then we obtain another cover of $C$ which also constitutes a path in the interval graph from $l$ to $r$.

We have reduced the problem of covering $C$ to finding the shortest path in an interval graph. This is solvable in time $O(n\log n)$ and space $O(n)$, as shown for example in An Optimal Algorithm for Shortest Paths on Weighted Interval and Circular-Arc Graphs with Applications by Atallah, Chen and Lee.

Answer 2

Stage 1: Break down the problem to that of covering a single interval.

Find the union of pairs in $A$ as follows: Sort the intervals in $A$ by their starting position. Go over them to find the first point that is not covered. Create an interval for this part. Repeat this starting from the left point of the next interval. At the end we will have a list of non-overlapping intervals. Call it $C$.

Note that we can break down the problem to the problem of covering a single interval in $C$. There are no intervals in $A$ that intersect more than one interval in $C$. So the problem is reduced to the problem of covering a given interval $[l,r]$ with the smallest number of intervals from $A$.

Stage 2: Find the smallest cover for each interval in $C$ using dynamic programming.

We use dynamic programming. Note that we only need to care about the end-points of intervals in $A$ that fall in $[l,r]$.

Sort the intervals in the increasing order according to their right end-points. If an interval is contained in another one remove it (remove redundant intervals).

Let $I_1,\cdots,I_n$ be the list of intervals in $A$. Let $l_k$ and $r_k$ refer to the index of the left and right end-points of interval $I_k$. Let the end-points of intervals in $A$ be $l=p_1< \cdots < p_m=r$.

We will use the dynamic programming with the following table:

$T[j,k]= \text{the size of smallest cover of $[p_1,p_j]$ using the first $k$ intervals.}$

In the following we explain how to compute $T[j,k]$.

If $j > r_k$ we cannot cover the interval as it is the interval with the right most end-point among $I_1,\cdots,I_k$. So there is no covering and we save value $\infty$.

In case $j \leq r_k$, we consider two cases: we use $I_k$ or we don't use it.

If we use $I_k$, we look for the smallest cover of $[p_1,p_{l_k}]$ with the first $k-1$ intervals. So we look at $T[l_k,k-1]$ and add one.

If we don't use $I_k$, we look for the smallest cover of $[p_1,p_j]$ with the first $k-1$ intervals. So we look at $T[j,k-1]$.

$$T[j,k] = \begin{cases} \min \{T[j,k-1] ,T[l_k,k-1]+1\} & j \leq r_k \\ \infty & o.w. \end{cases}$$

Analysis: The worst-case running-time of the algorithm (on a RAM machine) is $O(n^2)$ where $n$ is the number of intervals.