# Check whether an interval is contained in a union of intervals

Initial Problem:

Given an interval $[A, B]$ and a set of intervals $S = \{[S_{11}, S_{12}], [S_{21}, S_{22}], [S_{31}, S_{32}], \ldots, [S_{N1}, S_{N2}]\}$ with $S_{11}\leq S_{21}\leq \cdots \leq S_{N1}$ output True if and only if $[A, B]$ is completely contained in the union of all intervals in $S$, and False otherwise.

What is the best-time-complexity algorithm we can do this? Surely, there is a way to do this in $O(N)$ naively but is there any technique we could use to, say, lower the complexity down to $O(\log N)$ or anything better than $O(N)$?

The problem requires $\Omega(n)$ time. Consider the interval $[A,B] = [0,N]$ and an algorithm for the problem. Whenever the algorithm queries $[S_{i1},S_{i2}]$, it gets the answer $[i-1,i]$. If the algorithm queries all intervals, then it knows that they cover $[A,B]$. Otherwise, the algorithm cannot tell. Indeed, suppose that it doesn't query $[S_{i1},S_{i2}]$, and that all other intervals are of the indicated form. If $[S_{i1},S_{i2}] = [i-1,i]$ then they cover $[A,B]$, but if $[S_{i1},S_{i2}] = [i-1/3,i-2/3]$ then they don't. Note that both inputs are legal (satisfy the constraint $S_{11} \leq S_{21} \leq \cdots \leq S_{n1}$).
• Does it also require $\Omega(n)$ time, if the additional constraint that $S_{i1}, S_{i2}\in\mathbb{N}$ holds? Doesn't then the adversary proof become problematic? – Jason May 28 '17 at 13:59