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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Jason May 28 '17 at 13:59
  • 1
    $\begingroup$ No, it's easy to fix the proof. I'll let you figure out how. $\endgroup$ – Yuval Filmus May 28 '17 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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