Problem
Here is a special "matching" problem: given a set A of n numbers and a set B of n numbers, form pairs (a1, b1), ... , (an, bn), with {a1, . . . , an} = A and {b1, . . . , bn} = B, so that the following cost function is minimized:
Consider the following "greedy" strategy to solve this problem: pick the pair (a, b) with the smallest difference |a - b| (a ∈ A, b ∈ B). Then remove a from A and b from B, and repeat.
i. Give a counterexample showing that this strategy is incorrect, i.e., it can sometimes give a non-optimal solution. Show your work!
ii. Give another greedy strategy that will solve this special matching problem (detailed pseudocode is required).
Prove that it always returns an optimal solution. Justify correctness and analyze running time.