# Check if current interval is overlapping some intervals, or is being overlapped

Let's say we have array of $K$ integers, and we have given $N$ intervals in the form $l_{i}, r_{i}$, both inclusive, the interval $i$ means that all elements in the range $[l_i, r_i]$ are covered. Our task is to check for any of those $N$ intervals is the interval $i$, or the range $[l_i, r_i]$ being covered twice or more. Look in the examples to make it clear.

Example

$N = 3$, we have the intervals $I = \{ (1, 3), (4, 6), (1, 7) \}$. Let's illustrate the intervals

1 2 3 4 5 6 7 8 9 10...
-----               -> Interval 1
-----         -> Interval 2
-------------       -> Interval 3


We can see that the elements that are being covered by Intervals 1 and 2, are already covered with Interval 3, so we should return one of those indexes.

Please note that $K = 10^9$, so we cannot store the whole array.

What I think

If we were able to store the whole array of $K$ members, we could easily solve with lazy propagation, and range minimum queries, but since we cannot do that, I think that we should create dynamic segment tree where we will keep only the ranges we need to store the value for.

For example, if we need only the range $[1, 128]$ we do not need to store the ranges $[1, 63]$ and $[64, 128]$. This will save memory and time, but is it enough fast to solve this problem, and what will be the time complexity for this solution if we assume that $N \leq 10^5$.

• How does $K$ relate to the problem? Sep 23 '17 at 15:28
• K doesnt really matter, I just wrote it to show that the intervals can go up to 10^9 Sep 23 '17 at 17:37

Hint: Sort $\{l_1,r_1,\ldots,l_N,r_N\}$ and replace the sorted list with $1,\ldots,2N$ to effectively reduce $K$ to $2N$.

(There might be better ways of solving the problem, but this reduction at least gets rid of the dependence on $K$.)

• Do you understand how $K$ relates to the problem? The OP does not mention $K$ neither in the problem statement nor in the example (except the range of $K$). Sep 23 '17 at 16:58
• We'll probably get an explanation in the comments. Sep 23 '17 at 16:59
• K doesnt really matter, i just wanted to show that the intervals can be up to 10^9 elements Sep 23 '17 at 17:36
• You say that since $K$ is too large, we cannot "store the array". Now you say that $K$ doesn't really matter. Which is correct? Sep 23 '17 at 18:18
• K is constant and it is too large that we cannot write a solution with O(K) memory. Sep 24 '17 at 7:47