For simplicity, let us find partners for boys who wish to dance with shorter girls. The other case is solved analogously, by swapping boys' and girls' heights. The following algorithm solves the problem:

solution := 0
for each boy
    find the tallest girl without a partner shorter than him
    if no girl was found, continue
    pair up the current boy and the girl
    solution := solution + 1

A naive implementation of this algorithm has complexity ~\mathcal O(N^2)~ and is worth ~60\%~ of points. A key observation is that boys will be paired up with increasingly shorter girls if we iterate over boys from the tallest to the shortest one. This can be implemented with complexity ~\mathcal O(N \log N)~ or ~\mathcal O(N+H)~, where ~H~ is the maximum height difference. Alternatively, a solution with complexity ~\mathcal O(NH)~ is also worth all points.

Proof of Correctness

Let us denote by ~b~ and ~g~ the boy and the girl, respectively, in the first dance pairing we've made. In every optimal pairing, at least one of them will be paired up. Let us consider two cases:

1. Only one of them has a partner.

   Without loss of generality, assume that the boy ~b~ is the one who has a partner. If we pair up ~b~ with ~g~ instead of his current partner ~g_2~, the number of pairs doesn't decrease.

2. Both the boy and the girl have a partner.

   Let ~b~ be paired up with a girl ~g_2~, and ~g~ with a boy ~b_2~. ~g_2~ cannot be taller than ~g~. ~b_2~ is taller than ~g~, therefore he is also taller than ~g_2~. Thus the number of pairs doesn't decrease if we pair up ~b~ with ~g~ and ~b_2~ with ~g_2~.

The first pairing reduces the problem to a smaller problem, which can be solved by the same algorithm.