Finding a segment which has equal number of segments before and after it 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 &lt; b_i$.
write an algorithm which find a segment that the number of segments $[a_l ,b_l]$ before it $(b_l &lt; a_i)$ are equal to the number of segments $[a_r ,b_r]$ after it $(b_i &lt; 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:


 running heapsort by $a_i$ (runs in $O(n\log n)$)
 running bucket sort by $b_i$ which each bucket is $a_i$ (runs in $(O(n))$)
 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)$) 
 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)$)
 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?
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.


Sort all the $\{a_i,b_i\}$ together. Call the resulting sequence $(x_1,\ldots,x_{2n})$.
Set $n_a\gets0$, $n_b\gets0$.
Loop for $n_b$: For $t$ going from $1$ to $2n$ do:


If $x_t=b_i$ for some $i$, increment $n_b$
Else if $x_t=a_j$ for some $j$, set $L_j\gets n_b$

Loop for $n_a$: For $t$ going from $2n$ down to $1$ do:


If $x_t=a_i$ for some $i$, increment $n_a$
Else if $x_t=b_j$ for some $j$, set $R_j\gets n_a$

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
Final loop: For $i$ going from $1$ to $n$


If $L_i=R_i$, return $i$

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}$.