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 ai be the ith element of set A, and let bi be the ith element of set B. You then receive a payo? of Qn i=1 a bi i
Give an e?cient algorithm that will maximize your payo?. Prove that your algorithm maximizes the payo?, and state its running time