Check whether an interval is contained in a union of intervals
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}$).