3
$\begingroup$

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)$?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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}$).

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user21069
    May 28, 2017 at 13:59
  • 1
    $\begingroup$ No, it's easy to fix the proof. I'll let you figure out how. $\endgroup$ May 28, 2017 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.