Maximizing Revenue in Online Ad Placement

Problem

You are tasked with distributing n advertisements across n slots on a webpage to maximise the total revenue. Each advertisement offers a profit per click ai, and each slot has a predicted number of clicks per day bi.

To achieve the maximum revenue, you need to assign pairs (ai, bj) in such a way that the sum of the products of the pairs is maximised.

Examples

Example 1

Input: a = [23], b = [39]
Output: 897
Explanation: 
With one ad slot (`n=1`), pair the profit `23` with the clicks `39`.
Total revenue = 23 * 39 = 897.

Example 2

Input: a = [-5, 1, 3], b = [-2, 1, 4]
Output: 23
Explanation: 
After sorting, `a = [-5, 1, 3]` and `b = [-2, 1, 4]`.
Revenue calculation: (-5)*(-2) + 1*1 + 3*4 = 10 + 1 + 12 = 23.

Solution

Method 1 - Finding max index

The function max_dot_product attempts to calculate the maximum dot product of two arrays by iteratively:

1. Finding the max value from array a and array b using get_max_index.
2. Multiplying the two maximum values and adding the result to a cumulative summation, res.
3. Deleting the selected maximum values from both arrays (del a[max_a] and del b[max_b]).
4. Repeating the above process for all elements of the arrays (len(a) iterations).

Pseudocode

def max_dot_product(a, b):
	res = 0
	for i in range(len(a)):
		max_a = get_max_index(a)
		max_b = get_max_index(b)
		res = res + a[max_a] * b[max_b]
		del a[max_a]
		del b[max_b]
	return res

def get_max_index(array):
	max = array[0]
	index = 0
	for i in range(len(array)):
	if max < array[i]:
	max = array[i]
	index = i
	return index

Complexity

• ⏰ Time complexity: O(n^2)
  • get_max_index(array): Requires a full scan of the array to find the maximum value and its index, which takes O(n) for each call.
  • For n iterations, finding the maximum in two arrays (a and b) repeatedly makes this approach cost O(n^2) due to nested iterations.
• 🧺 Space complexity: O(n)

Method 2 - Sorting

Reasoning or Intuition

To achieve maximum revenue:

• Pair the highest profit-per-click (ai) with the highest number of clicks per day (bi), the second highest profit with the second highest clicks, and so on.
• Sorting both arrays in descending order ensures every high-value profit matches with every high-value click.

Approach

1. Input Parsing: Take the values of n, and the sequences of a (profit-per-click) and b (expected clicks) from input.
2. Sorting: Sort both sequences in descending order.
3. Pairing: Iterate and calculate the maximum revenue by summing the products of the corresponding pairs.
4. Output: Return the computed maximum revenue.

Code

C++

class Solution {
public:
    int maximiseRevenue(int n, vector<int>& profits, vector<int>& clicks) {
        // Sorting both arrays in descending order
        sort(profits.rbegin(), profits.rend());
        sort(clicks.rbegin(), clicks.rend());
        
        // Calculate maximum revenue
        int revenue = 0;
        for (int i = 0; i < n; ++i) {
            revenue += profits[i] * clicks[i];
        }
        return revenue;
    }
};

int main() {
    int n = 3;
    vector<int> profits = {1, 3, -5};
    vector<int> clicks = {-2, 4, 1};
    Solution solution;
    cout << solution.maximiseRevenue(n, profits, clicks) << endl;
    return 0;
}

Java

class Solution {
    public int maximiseRevenue(int n, int[] profits, int[] clicks) {
        // Sort both arrays in descending order
        Arrays.sort(profits);
        Arrays.sort(clicks);
        
        // Calculate maximum revenue
        int revenue = 0;
        for (int i = 0; i < n; i++) {
            revenue += profits[n - 1 - i] * clicks[n - 1 - i];
        }
        return revenue;
    }
    
    public static void main(String[] args) {
        int n = 3;
        int[] profits = {1, 3, -5};
        int[] clicks = {-2, 4, 1};
        Solution solution = new Solution();
        System.out.println(solution.maximiseRevenue(n, profits, clicks));
    }
}

Python

class Solution:
    def maximiseRevenue(self, n, profits, clicks):
        # Sort profits and clicks in descending order
        profits.sort(reverse=True)
        clicks.sort(reverse=True)
        
        # Maximise revenue
        revenue = sum(p * c for p, c in zip(profits, clicks))
        return revenue


# Example Usage
n = 3
profits = [1, 3, -5]
clicks = [-2, 4, 1]
solution = Solution()
print(solution.maximiseRevenue(n, profits, clicks))

Complexity

• ⏰ Time complexity: O(n log n)
  • Sorting both arrays costs O(n log n) time.
  • Summing the products of the elements costs O(n) time.
  • Overall Time Complexity = O(n log n).
• 🧺 Space complexity: O(1), Sorting and computation are done in-place, using only constant extra space.