Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|cite|improve this question
Your algorithm is not correct as it will not find the smallest size cover, it will find only a minimal one. – Kaveh Feb 6 '13 at 1:29
So you have a set of intervals and want to cover them with as few of them as possible. – Raphael Feb 6 '13 at 7:53

2 Answers 2

up vote 7 down vote accepted

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.

share|cite|improve this answer
If you don't like $(x,x+\epsilon)$, replace it with $(2x,2x+1)$. (Assuming all the numbers are integral.) – Yuval Filmus Feb 7 '13 at 5:12

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.

share|cite|improve this answer
I have a question (couple of years later :). In stage 2, when we have to cover one interval, and we have sorted the appropriate intervals of $A$ by right endpoint, why doesn't a simple greedy search work? That is, starting at $r$, choose an interval with the furthest left endpoint $l_0$; then, do the same thing for intervals whose right endpoint is to the right of $l_0$; continue this way until all intervals are processed. This seems like it's linear in the number of intervals covering $[l,r]$. – Steve D Nov 19 at 23:22
@Steve, I haven't thought about for some time but it looks greedy can work: among intervals that intersect with the last picked interval, pick the one that has the rightmost right endpoint. We have to pick an interval which intersects with the previous one and there is no harm in choosing the one with the rightmost right endpoint. – Kaveh Nov 20 at 4:14
OK, good to know. The article Yuval linked was a little much for me, but it's nice that this answer can be adapted to linearithmic time as well. Thanks! – Steve D Nov 20 at 4:56
@Steve, it is still $n \lg n$ because of sorting. – Kaveh Nov 20 at 5:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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