Maximize Minimum Customer Satisfaction
Preview mode. Log in to edit, run, submit, and save progress.
Maximize Minimum Customer Satisfaction
You are given ratings of m products by n customers. Choose exactly n - 2 products. For each customer, their satisfaction is the maximum rating they gave among the chosen products. Find the maximum possible value of the minimum satisfaction across all customers.
Examples
n = 4 , m =4 [3 4 2 2 3 3 3 4 2 4 2 3 4 2 4 2]
3
Explanation: we must choose: n - 2 = 2 products Try choosing products 0 and 1. Customer 1: max(3, 4) = 4 Customer 2: max(3, 3) = 3 Customer 3: max(2, 4) = 4 Customer 4: max(4, 2) = 4 Now take the minimum: min(4, 3, 4, 4) = 3 No product pair can give a value greater than 3, so the answer is: 3
Approach hint
maximum rating in that customer's row among selected columns
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.