World's most popular travel blog for travel bloggers.

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

, , No Comments
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

Answered By : jadhachem

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44335

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback