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:
- 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?
low[x]
Please use LaTeX for the math formulae. $\endgroup$