0
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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$). $\endgroup$ – fade2black Sep 23 '17 at 16:58
  • $\begingroup$ We'll probably get an explanation in the comments. $\endgroup$ – Yuval Filmus Sep 23 '17 at 16:59
  • $\begingroup$ K doesnt really matter, i just wanted to show that the intervals can be up to 10^9 elements $\endgroup$ – someone12321 Sep 23 '17 at 17:36
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Sep 23 '17 at 18:18
  • $\begingroup$ K is constant and it is too large that we cannot write a solution with O(K) memory. $\endgroup$ – someone12321 Sep 24 '17 at 7:47

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.