Maximize Payoff by Greedy Reordering

Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 384, Problem 16.2-7

Problem:
Suppose you are given two sets $A$ and $B$, each containing $n$ positive integers. You can choose to reorder each set however you like. After reordering, let $a_i$ be the $i$th element of set $A$, and let $b_i$ be the $i$th element of set $B$. You then receive a payoff of $\prod_{i=1}^{n}{a_i^{b_i}}$. Given an algorithm that will maximize your payoff. Prove that your algorithm maximizes the payoff, and state its running time.

Solution:
Greedy Algorithm: Let the set $\{a_i\}$ be sorted so that $a_1 \ge a_2 \ge \ldots \ge a_n$ and set $\{b_i\}$ be sorted so that $b_1 \ge b_2 \ge \ldots \ge b_n$. Pair $a_i$ with $b_i$. This is the required solution.

Complexity:
If the two sets $A$ and $B$ are already sorted, the time complexity is $O(n)$.
If the sets are not sorted, then sort them first and the time complexity is $O(n\log n)$.

Proof:
Suppose the optimal payoff is not produced from the above solution. Let $S$ be the optimal solution, in which $a_1$ is paired with $b_p$ and $a_q$ is paired with $b_1$. Note that $a_1 \gt a_q$ and $b_1 \gt b_p$.

Consider another solution $S'$ in which $a_1$ is paired with $b_1$, $a_q$ is paired with $b_p$, and all other pairs are the same as $S$. Then $$\frac{\text{Payoff}(S)}{\text{Payoff}(S')}=\frac{\prod_{S}\hspace{2 mm} a_i^{b_i}}{\prod_{S'}\hspace{2 mm}a_i^{b_i}}=\frac{(a_1)^{b_p} (a_q)^{b_1}}{(a_1)^{b_1} (a_q)^{b_p}}=(\frac{a_1}{a_q})^{b_p - b_1}$$ Since $a_1 \gt a_q$ and $b_1 \gt b_p$, then $\text{Payoff}(S) / \text{Payoff}(S') \lt 1$. This contradicts the assumption that $S$ is the optimal solution. Therefore $a_1$ should be paired with $b_1$. Repeating the argument for remaining elements, we can get the result.