I was solving a problem where we have k intervals, and we need to count the number of nested pairs.
More formally, count pairs (i, j) such that:
l_i < l_j <= r_j < r_i
(or equivalently after sorting by the left endpoint, count previous intervals whose right endpoint is greater than or equal to the current one).
The standard solution is:
- Sort intervals by the left endpoint.
- Insert right endpoints into an
ordered_set(PBDS). - Use
order_of_key()to count how many previous right endpoints are greater than or equal to the current one.
This gives an O(n log n) solution.
My question is:
Is there an O(n log n) or O(n) solution that does not use PBDS (ordered_set), GNU extensions, or similar policy-based data structures?
I'm looking for alternatives using only standard C++ (STL). Thanks!
Auto comment: topic has been updated by Thrb_73 (previous revision, new revision, compare).
Segment trees or Binary search trees can do that in O(nlogn).
Thanks for your answer!
I was actually looking for a solution that doesn't rely on advanced data structures like Segment Trees, Fenwick Trees, or balanced BSTs/PBDS.
I was wondering if there's a simpler algorithm using only basic STL containers and techniques, or if such a solution simply doesn't exist.
Suffix-sum can also do this.
Thanks! Could you explain that approach a bit more?
I'm not sure how suffix sums can be used here after sorting the intervals. A brief explanation or pseudocode would be really helpful.
You need to discrete all the l and r.
And update the suffix sum
Wait my solution was wrong it can up to $$$O(n^2)$$$
Maybe you can use a Fenwick Tree.
Observe that any two segments can be either completely separate, partially overlapping (including sharing a border), or nested. For each segment $$$i$$$ only consider those that start strictly before it ends. Then the number of nested segments is those that end strictly before $$$r_i$$$ minus those that end strictly before $$$l_i$$$ and those that start before or at $$$l_i$$$ and end strictly before $$$r_i$$$.
Do coordinate compression so $$$l_i,r_i\le 2n$$$. This takes $$$O(n\log n)$$$ time.
For each $$$l$$$ and $$$r$$$ value, make a vector of the segments that start and end here, respectively. Call those $$$s_i$$$ and $$$t_i$$$ respectively.
Iterate $$$i$$$ over the values from left to right while maintaining a running count of how many open segments there are and how many closed segments there are (both initially 0).
At each value perform the following:
a. Store the open and closed running counts in $$$o_i$$$ and $$$c_i$$$, respectively.
b. Iterate $$$j$$$ through $$$t_i$$$ and add $$$c_{r_j}-c_{l_j}-o_{l_j}$$$ to the final answer.
c. Update the running counts by adding $$$|t_i|$$$ to the closed count and adding $$$|s_i|-|t_i|$$$ to the open count.
Thank you! That makes sense now. I really appreciate your detailed explanation.