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).
- Show an algorithm for the general case.
- 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)$?