2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Welcome to Computer Science Stack Exchange. Questions like: please check my proof or my algorithm are not on-topic here. We expect you to have a precise question on issues you consider problematic in the work yo have done, and to ask a specific question about that. Also, make efforts to answer precisely questions in comments. See for example my edit to your question. BTW, what is low[x] Please use LaTeX for the math formulae. $\endgroup$ – babou Jul 12 '15 at 10:04
  • $\begingroup$ Thanks babuo for editing and make the post more clear! :) I'm a student and this is a topic about CS - so it is on-topic: cs.stackexchange.com/help/on-topic I'm using Stack Exchange a lot in my studies, and couldn't find a question similar to that in google, so probably it's going to be useful for someone else in the future. $\endgroup$ – Nir Tayeb Jul 16 '15 at 10:40
  • 2
    $\begingroup$ As babou correctly states, "please check my algorithm" problems are not on-topic here, because they already include a complete answer to the original problem but no question about this answer; thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here for more information about this policy. Asking whether an algorithm faster than $O(n \lg n)$ exists is on-topic here, though. $\endgroup$ – D.W. Jul 17 '15 at 0:28
  • 1
    $\begingroup$ Therefore, I think the "Am I right?" part is not a suitable question. Also "Is there a better solution" is not suitable, as you haven't defined what would count as better. Do you want faster asymptotic runtime? A simpler algorithm? Something else? I suggest editing your question to clarify. In general, cs.stackexchange.com/help/on-topic is intended as guidance but does not have a comprehensive list of all of the policies; you're welcome to visit us on Computer Science Meta for more if in doubt. $\endgroup$ – D.W. Jul 17 '15 at 0:28
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That's a lot of pseudocode. Can you explain the main idea behind it? What is its running time? How does it answer the question? Is it better than the algorithm provided in the question, and if so, how? In particular, the running time of this algorithm is also $O(n \lg n)$, so it doesn't appear to be faster than the algorithm provided in the question. $\endgroup$ – D.W. Jul 17 '15 at 0:33
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.