# Counting pairs of intervals where one is a subset of the other

Given a list of intervals with nonnegative endpoints, e.g. $$[3,5][1,7][2,60]$$, the goal is to find the number of pairs of intervals $$I,J$$ such that $$I$$ is a subset of $$J$$. In this particular case the total number is 2 because $$[3,5]$$ is a subset of $$[1,7]$$ and a subset of $$[2,60]$$. Furthermore we were asked to find a solution to this problem with time complexity less than $$O(n^2)$$.

At first I thought of sorting the given sets based on their lower bound and in this example the order would be $$[1,7] \to [2,60] \to [3,5]$$ so the time complexity so far is $$O(n\log n)$$, but I can tell nothing about the total number of pairs cause of the order of the upper bounds of the sets is a mess. Then I thought of sorting them based on their middle element and then performing a Binary Search based on this sorting so my time complexity would still be $$O(n\log n)$$. However now I am stuck and a direction would be appreciated.

Sort all endpoints of intervals, and maintain a self-balancing order statistic tree, initially empty. Scan the endpoints from left to right. Add each left endpoint to the tree. When reaching a right endpoint, determine the order statistic of the left endpoint, and then remove the endpoint. Update the number of intersections accordingly: if the left endpoint was that $$i$$th smallest element (counting from $$1$$), then add $$i-1$$.

Since each operation on a self-balancing order statistic tree takes $$O(\log n)$$, the entire algorithm runs in $$O(n\log n)$$.

As an example, consider your list of intervals.

• Initially, the tree is empty, and the counter is 0.
• Read left endpoint of [1,7]. Tree contains 1.
• Read left endpoint of [2,60]. Tree contains 1,2.
• Read left endpoint of [3,5]. Tree contains 1,2,3.
• Read right endpoint of [3,5]. Since 3 is the third smallest point, increase counter by 2. Tree contains 1,2.
• Read right endpoint of [1,7]. Since 1 is the smallest point, increase counter by 0. Tree contains 2.
• Read right endpoint of [2,60]. Since 2 is the smallest point, increase counter by 0. Tree is empty.