Finding a segment which has equal number of segments before and after it

Question

I got this question in a past test that I'm trying to solve but i don't have the solutions to check my self:

Given a set of n segments $[a_i ,b_i]$ where $i=1,..,n$ and $a_i < b_i$. write an algorithm which find a segment that the number of segments $[a_l ,b_l]$ before it $(b_l < a_i)$ are equal to the number of segments $[a_r ,b_r]$ after it $(b_i < a_r)$ the algorithm will return its index if found else null

The algorithm should work in $O(n\log n)$ in worst case.

My solution is:

1. running heapsort by $a_i$ (runs in $O(n\log n)$)
2. running bucket sort by $b_i$ which each bucket is $a_i$ (runs in $(O(n))$)
3. loop on each member (X) in reverse order and finding using binary-sort on the rest of the set the segment (Y) which its $b_i$ is equal or max close to $a_i$ and writing in the Y the distance of X from the end of list (number of segments which are right of Y) and writing in X the index of Y (number of segments which are left of X). that happens in (runs in $O(nlgn)$)
4. loop on each member the looking up for an element with (left_count equals right_count) not equals zero and return it (runs in $O(n)$)
5. if nothing found - return null

So finally the algorithm works in $2lgn + 2n$ which is $O(nlgn)$

Am I right? There is a better solution?

Answer 1

Here is an algorithm that achieves $O(n\log n)$ complexity without any elaborate data structures. Just a simple sort and a couple of loops.

1. Sort all the $\{a_i,b_i\}$ together. Call the resulting sequence $(x_1,\ldots,x_{2n})$.
2. Set $n_a\gets0$, $n_b\gets0$.
3. Loop for $n_b$: For $t$ going from $1$ to $2n$ do:
   1. If $x_t=b_i$ for some $i$, increment $n_b$
   2. Else if $x_t=a_j$ for some $j$, set $L_j\gets n_b$
4. Loop for $n_a$: For $t$ going from $2n$ down to $1$ do:
   1. If $x_t=a_i$ for some $i$, increment $n_a$
   2. Else if $x_t=b_j$ for some $j$, set $R_j\gets n_a$
5. Now for each interval $[a_i,b_i]$, $L_i$ and $R_i$ contain the number of intervals to its left and to its right, respectively
6. Final loop: For $i$ going from $1$ to $n$
   1. If $L_i=R_i$, return $i$
7. Found nothing: Return null.

You might need to make some additional checks to take care of cases where $a_i=b_j$ for $i\not=j$.

Note that equality checks of the form $x_t=b_i$ can be done by saving the sorting indices. In other words, if you sort an array $u$ into another array $v$, you can save indices $\pi_t$ such that $u_t=v_{\pi_t}$.

Answer 2

$O(n \lg n)$ time is achievable without any fancy techniques. So, yes, there is a better solution, if "conceptually simpler" and "simpler to implement" counts as better.

Store all of the intervals in a segment tree. Augment the data structure so that each node stores the number of intervals to the right of that node; as well as the number of intervals to the left of that node. These values can be filled in easily by a bottom-up traversal. Now a simple linear scan can be used to check whether such a segment exists.

The running time is $O(n \lg n)$: it takes $O(n \lg n)$ time to build the tree, $O(n)$ time to do the bottom-up traversal, and $O(n \lg n)$ time to check all the segments (since a segment can be looked up in the tree in $O(\lg n)$ time), for a total of $O(n \lg n)$ time.

---

Can you find an algorithm that is asymptotically faster than $O(n \lg n)$ time? Well, any algorithm that involves sorting will automatically take $\Omega(n \lg n)$ time (under semi-reasonable models), so no such algorithm can be faster than $O(n \lg n)$ time.

It might possible to achieve $O(n)$ time, using fancy techniques -- in particular, by trying to adapt QuickSelect to this problem -- but the resulting algorithm will likely be more complex, so if ease of implementation is a significant factor, such an approach might not better in practice.