To minimize ~D~, it turns out that it's always optimal to pair the worst cow with the worst monkey, the second-worst cow with the second-worst monkey, and so on. To prove this, let's consider a pair of cows with combat skill levels ~C_1~ and ~C_2~ (such that ~C_1 < C_2~), and a pair of monkeys with combat skill levels ~M_1~ and ~M_2~ (such that ~M_1 < M_2~). We note that forming the pairs ~(C_1, M_2)~ and ~(C_2, M_1)~ can never be better than forming the pairs ~(C_1, M_1)~ and ~(C_2, M_2)~. In other words, ~\max(|C_1-M_2|, |C_2-M_1|) \ge \max(|C_1-M_1|, |C_2-M_2|)~.

Having made this insight, we'll want to sort the two lists ~C_1, \dots, C_N~ and ~M_1, \dots, M_N~ in non-decreasing order, which can be done in ~\mathcal O(N \log N)~ time. We can then simply find and output the maximum value of ~|C_i-M_i|~ over ~i = 1 \dots N~.