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.