World's most popular travel blog for travel bloggers.

# [Answers] Finding a segment which has equal number of segments before and after it

, ,
Problem Detail:

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?

###### Asked By : Nir Tayeb

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