2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.