1
$\begingroup$

I've seen similar questions around here but I'm trying to address this problem with a slight change and maybe it makes it easier to solve.

I'm given a set of intervals $\{s_1,s_2,...,s_n\}$ where each interval has a starting point $b_i$ and an ending point $r_i$. Also, the set is not changing meaning no new intervals are inserted or removed, and no end/start points are identical.

I want to be able to return the number of intervals in $O(\log(n))$ time. I am aware of an interval tree however I actually don't have to worry about insertions and deletions so there might be something simpler.

Also, say I use an AVL tree where I use the start points as keys, and in each node I hold:

  • start - the start point of the interval
  • end - the end point of the interval
  • max - the max end point of an interval that is contained in the tree initiated at this node

And I search like so:

Given a point $p$, I start at the root and go down based on the max value compared to the point. If $p$ is greater than the max of the node, I'm currently at I consider it's right sub-tree. If $p$ is smaller than max, I consider the right sub-tree until I hit null or I find an interval that contains the point(based on start and end points).

This algorithm can return an interval that contains $p$ in $O(\log(n))$ time, but what if I wanna return the number of all intervals that contain it?

I understand it can be done in $O(\log(n)+k)$ time, where $k$ is the number of intervals containing the point but can't see really how.

$\endgroup$
  • $\begingroup$ "This algorithm can return an interval that contains $p$ in $O(\log(n))$ time". You do not include the time it takes to build an AVL tree, do you? Do you mean the algorithm should preprocess all $[b_i,r_i]$, whose time-complexity should not be included? $\endgroup$ – Apass.Jack May 16 at 12:49
  • $\begingroup$ The time it takes to preprocess is not included, just retrieving the intervals that contain that point. $\endgroup$ – sadElephent May 16 at 13:45
  • 1
    $\begingroup$ Are you aware of the segment tree? $\endgroup$ – xskxzr May 18 at 7:35
1
$\begingroup$

It is a very strong assumption that the time it takes to preprocess is not a concern.

Assume each given interval contains both of its endpoints. Otherwise, the solution below can be adapted easily.

Sort all $b_i$ and $r_i$ into an increasing sequence $A=(a_1, \cdots, a_{2n})$. Let $c_1=1$. For $i$ from 2 to $2n-1$, let $$c_{i}=\begin{cases} c_{i-1}+1&\text{ if } a_{i}\text{ is a starting point of a given interval,}\\ c_{i-1}-1&\text{ if } a_{i}\text{ is an ending point of a given interval.} \end{cases}$$ $c_i$ is the number of the given intervals that contain the open interval $(a_i, a_{i+1})$ for $1\le i\le 2n-1$. Let $C$ be the sequence $(c_1, \cdots, c_{2n-1})$. The combination of $A$ and $C$ is what we wanted from preprocessing.

Given any number $p$, if $p \gt a_1$ and $p\lt a_{2n}$, we can find the largest index $i$ such that $p\ge a_{i}$ by binary search in $O(\log n)$ time. Then the number of given intervals that contain $p$ is given by $$\begin{cases} 0&\text{ if } p<a_1,\\ 1&\text{ if } p= a_1,\\ c_{i}&\text{ if } a_i<p\lt a_{i+1}\text{ or } p=a_i\text{ and } c_i>c_{i-1},\\ c_{i}+1&\text{ if } p=a_i\text{ and } c_i<c_{i-1},\\ 1&\text{ if } p=a_{2n},\\ 0&\text{ if } p>a_{2n},\\ \end{cases}$$ In other words, we can get the answer in $O(\log n)$ time once $A$ and $C$ are known.

$\endgroup$

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.