Solution: Maximum Advertisement Revenue

Solution 1: Assign the most valuable ad to the most popular place

You wouldn’t be surprised to hear that a greedy strategy maximizes the revenue. Assume that $clicks_{p}$ and $price_{q}$ are the largest elements: $clicks_{p}$ $≥$ $clicks_{i}$ and $price_{q}$ $≥$ $price_{i}$ for all $i$ = $1,\ldots,$$n$. We claim that there exists an optimum solution that pairs $clicks_{p}$ with $price_{q}$. To prove this, consider an optimum solution and assume that it pairs $clicks_{p}$ with $price_{q}$ ...