Listing all intervals that overlap interval i in O(min(n, k lg n)) where k is the number of overlapping intervals

Question

This question is exercise 14.3-4 in Introduction to Algorithms, Second Edition.

14.3-4: Given an interval tree T and an interval i, describe how all intervals in T that overlap i can be listed in O(min(n, k lg n)) time, where k is the number of intervals in the output list. (Optional: Find a solution that does not modify the tree.)

I don't want to modify the tree. I've thought of this algorithm (and also found it on a few websites that offer solutions to the book):

INTERVAL-LIST(T, i):
x ← root[T]
if int[x] overlaps i then
    LIST-INSERT(L, int[x])
if left[x] ≠ nil[T] and max[left[x]] ≥ low[i] then
    INTERVAL-LIST(left[x], i):
if right[x] ≠ nil[T] and max[right[x]] ≥ low[i] and low[int[x]] ≤ high[i] then
    INTERVAL-LIST(right[x], i)
return L

I understand why max[left[x]] ≥ low[i] guarantees that an interval which overlap i exists in the subtree left[x]. But I don't think that the condition max[right[x]] ≥ low[i] and low[int[x]] ≤ high[i] guarantees that.

For example if int[x] = [16,30] and int[right[x]] = [35,36] and i = [32,33] then the condition is satisfied, but [35,36] does not overlap i (subtree right[x] does not have any more nodes).

Answer 1

Neither condition guarantees the existence of an overlapping interval, both merely mean that you cannot reject the subtree right away.

Also, I don't believe it is at all possible to do it in O(min(n, k lg n)) at all. If the interval doesn't overlap at all (k=0) then O(min(n, k lg n)) is effectively O(1), so you'd have to find in constant time whether i overlaps with any of the intervals in T.

Answer 2

Glad I found this, I have also been looking at several other folks "solutions" like the one you mention wondering how it could be that "it only branches when there is a guaranteed overlapping interval in the subtree".

I do think the problem is O(k lg(n)) though (for k != 0 anyway): One method is to repeatedly use INTERVAL-SEARCH to find an overlapping set (which cost you O(lg(n)) and delete that node (which in a red-black tree costs you O(lg(n))). Stop when INTERVAL-SEARCH returns T.nil.