I have a series of line segments $l_i=(a_i,b_i)$ with $i=1,2,3...n$

$a_i$ and $b_i$ are their starting and ending points coordinates in $x$ axis.

The question is how to find a algorithm that is strictly cheaper than $O(n^2)$ and it yields number of pairs $i,j$ such that $l_j$ completely contains $l_i$ and $j>i$.

I know that without the second constraint, we can just sort the segments by their starting points and do the inversion counting for the ending points.

However, if we want to satisfy the second constraint, what is the optimal way? I was thinking maybe I could maintain an augmented BBST and the key is just the starting point of each segment, once we insert a new segment, there may be some efficient way to count how many nodes in the tree have smaller ending points than the one I just insert.

  • $\begingroup$ You tagged this divide-and-conquer. Have you tried a divide-and-conquer algorithm? Can you split the set of $n$ intervals into two smaller sets of size $n/2$ somehow, and then do something? I'd suggest that you keep trying: spend a bit more time on this and try a few more approaches, then edit to show us those attempts. $\endgroup$ – D.W. Mar 9 '17 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.