2
$\begingroup$

Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(\min(n,(k + 1) \log n))$ where $k$ is the number of intervals returned. The only solution I can think of is bruteforcing in $O(n)$ time, but that's clearly too simple.
While looking for an answer I came across stabbing queries and the problem seemed very similar to this one. Is this something I could base my algorithm on or am I on the wrong track?

Edit: I might have an idea, but I'm still missing something.
Let $I=[I_s,I_e]$ and $x$ a node. If $x.s \leq I.s$ then there is an interval that contains $I$ in the left subtree of $x$ if and only if $\mathrm{left}[x].\max\geq I.e$. Suppose you had a similar statement for the right subtree of $x$, then you could do the following:
If the condition for the left or/and subtree is satisfied, recurse on those trees. Since there must be an interval covering $I$ in these subtrees this will result in $k$ paths with a maximum length of $\log n$.
If $x.s > I.s$ there can't be an interval in the right subtree that covers $I$, but there might be one in the left, so recurse on left. If this happens repeatedly until you find a leaf, you get a path of length $logn$ without finding anything.

My question is: given $x.s \leq I.s$, how can I know for sure whether the right subtree of $x$ contains an interval covering $I$?

$\endgroup$
1

2 Answers 2

0
$\begingroup$

Hint: A (non-root) interval can only contain I if its parent contains I.

For the algorithm in the pseudo-code below, TestInterval is not called for the same vertex twice, so the complexity is $O(n)$.

Consider the subtree S consisting of all nodes which TestInterval is called on. At every node in S which is not a leaf node, an interval must have been added to intervalContainingI (and k incremented). A binary tree with k non-leaf nodes can have at most $k+1$ leaf nodes. Therefore the complexity is in fact $O(k)$.

vector<int> intervalsContainingI;

void TestInterval(interval x)
{
    if (x.start <= I.start && x.end >= I.end)
    {
        intervalsContainingI.push_back(x);
        if (Exists(x.leftChild))
        {
            TestInterval(x.leftChild);
        }
        if (Exists(x.rightChild)
        {
             TestInterval(x.rightChild);
        }
    }
}

TestInterval(root_node);
$\endgroup$
1
  • $\begingroup$ I was wondering if your solution works with the same kind of tree as mine. My assignment defines an interval tree as a binary search tree ordered by the left endpoints of the intervals. Each node also stores the maximum right endpoint from the subtree rooted at that node. In that case you could have an interval that contains I while its parent doesn't, right? For example: parent = [2,5], child = [3,7], I = [3,6]. $\endgroup$
    – Algebro
    Mar 18, 2017 at 21:24
0
$\begingroup$

If the nodes contain a max_end attribute in addition to the interval, you can use the max_end to stop looking further down the tree.

def find_containing_intervals(interval, root_node):
    stack = [root_node]
    containing_intervals = []
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if node.max_end < interval.end:
            continue
        if node.interval.contains(interval):
            containing_intervals.append(interval)
        if node.interval.start <= interval.start:
            stack.append(node.right_child)
        stack.append(node.left_child)

    return containing_intervals

Recursive solution:

class Node:
    def find_containing(self, interval):
        intervals = []
        if self.max_end < interval.end:
            return intervals
        if self.interval.contains(interval):
            intervals.append(interval)
        if self.right_child is not None and self.interval.start <= interval.start:
            intervals.extend(self.right_child.find_containing(interval))
        if self.left_child is not None:
            intervals.extend(self.left_child.find_containing(interval))
        return intervals
$\endgroup$

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.