I have been wondering over the following problem:

Given a set $S$ of intervals on the number line. We can do two operations on them:

  1. Add a new interval $[l_i,r_i]$ to $S$
  2. Given an interval $[l_j, r_j]$, which is possibly not in $S$, find the longest interval from $S$ which is contained entirely in $[l_j, r_j]$

If I didn't have operation $1$ I have found a solution using a persistent segment tree.

For the full version, there is the trivial solution which runs in $O(QN)$ ($Q$ - number of queries, $N$ - total number of intervals added). I also found that using interval tree, I can directly find which intervals intersect the query interval and then I can check them manually. However, is there an even better solution? Maybe $O(Q\log N)$ or $O(Q\log^2N)$?

  • $\begingroup$ @thefunkyjunky Please add a reference to the original problem. $\endgroup$
    – John L.
    Commented Jul 4, 2019 at 14:35
  • $\begingroup$ @Apass.Jack sorry, I'll add explanations for Q and N. There is no original problem(you can say I made it up), that's why I am asking if there is a better solution. $\endgroup$ Commented Jul 4, 2019 at 16:18
  • $\begingroup$ I'm a bit confused about your notation. Your first bound is $O(QN)$, which makes me think that what you're measuring includes the time to process all queries. Your second bounds, however, don't include $Q$ at all. But if you're processing all queries, the answer must be at least $\Omega(Q)$, since you have to read every query. $\endgroup$
    – jbapple
    Commented Jul 7, 2019 at 22:00
  • $\begingroup$ @jbapple, fixed. $\endgroup$ Commented Jul 7, 2019 at 22:27
  • $\begingroup$ Can you describe your solution using a persistent segment tree? $\endgroup$
    – jbapple
    Commented Jul 7, 2019 at 22:32


Your Answer

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

Browse other questions tagged or ask your own question.