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

Improve this question
$\endgroup$
2
  • $\begingroup$ How does $K$ relate to the problem? $\endgroup$
    – fade2black
    Sep 23, 2017 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, 2017 at 17:37

1 Answer 1

Reset to default
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$.)

Improve this answer
$\endgroup$
7
  • $\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, 2017 at 16:58
  • $\begingroup$ We'll probably get an explanation in the comments. $\endgroup$
    – Yuval Filmus
    Sep 23, 2017 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, 2017 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, 2017 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, 2017 at 7:47

Your Answer

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

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