0
$\begingroup$

A producer wants to arrange couples of boys and girls for a dance.
There are n boys arranged in a row [A1...An] in some certain order and n girls arranged in a different row [B1...Bn], also in some certain order. Only a couple in which there is a boy and a girl with exactly the same height can dance.
The height of every boy and girl is known. The producer needs to find the maximum number of couples that can dance (There might be people who can't dance).

  1. Show an algorithm for the general case.
  2. Show an algorithm, in which you can't change the order of the boys and the girls. In other words: If there is a couple (Ai,Bj) then there can't be (Ak,Bp) (so that k > i, p < j or k < i, p > j)

Analyze the complexity in every case.

What I know is that the solution to 1 is sorting the array in $O(nlogn)$.
My idea in approaching 2 is that it's like LCS in a static table, only with numbers and not chars, which takes $O(n^2)$.

Can 2 be done in better complexity that $O(n^2)$?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Hint: Use dynamic programming. There might be more efficient algorithms, though. $\endgroup$
    – Yuval Filmus
    Commented Jun 1, 2014 at 8:27
  • 2
    $\begingroup$ What do you mean by 'general case' ? $\endgroup$
    – donkey
    Commented Jun 1, 2014 at 8:32
  • $\begingroup$ @sai_preet the general case is when you don't know anything about the two "strings" of boys and girls, so you just use LCS. $\endgroup$
    – HaloKiller
    Commented Jun 1, 2014 at 9:02
  • $\begingroup$ You did not mention that we need to maintain order of both boys and girls for the first case. $\endgroup$
    – donkey
    Commented Jun 1, 2014 at 9:50
  • 1
    $\begingroup$ So,for the first case why don't just sort the two arrays compare element of first array with second (like merge function in merge-sort). The complexity would reduce to $O(n log n)$ $\endgroup$
    – donkey
    Commented Jun 1, 2014 at 9:55

1 Answer 1

Reset to default
2
$\begingroup$

Longest common subsequence (not necessarily continuous) is the solution for the second problem, not for the first. (For the first problem it is not only slower than necessary, but also gives the wrong result. Consider e.g. $A=[1,2]$, $B=[2,1]$: LCS would give only 1 couple, while actually 2 can be formed.)

For the first problem, as @sai_preet pointed out in a comment, you can sort both arrays and then find the couples with a procedure analoguous to merge. This will take $\Theta(n\log n)$ time.

Improve this answer
$\endgroup$

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