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.