# Conditional LCS problem

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)$?

• Hint: Use dynamic programming. There might be more efficient algorithms, though. – Yuval Filmus Jun 1 '14 at 8:27
• What do you mean by 'general case' ? – preetsaimutneja Jun 1 '14 at 8:32
• @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. – HaloKiller Jun 1 '14 at 9:02
• You did not mention that we need to maintain order of both boys and girls for the first case. – preetsaimutneja Jun 1 '14 at 9:50
• 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)$ – preetsaimutneja Jun 1 '14 at 9:55

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.