FastPrep

Description

Solutions

Choose Max Min Rating

📚RELATED PROBLEMS

There are n customers and m products. Each customer gives a rating r[i] for each of the i'th product (This is stored in ratings 2d matrix). The task is to choose (n-2) products such that the min of the mx array is maximized. Where, mx[j] be the max rating given by a customer j for among all selected products.

Example 1:

Input:  n = 4, m = 4, ratings = [[3,4,2,2],[3,3,3,4],[2,4,2,3],[4,2,4,2]]
Output: 3 
Explanation:
      
        Here we have 4 customers and 4 products. Customer 1 gives rating of ratings[0] for the 4 products and so on. We need to choose (n-2) products such that the min of the mx array is maximized.
      
      
        If we choose product 0 and 1: min(max(3,4),max(3,3),max(2,4),max(4,2)) = 3

        If we choose product 0 and 2: min(max(3,2),max(3,3),max(2,2),max(4,4)) = 2

        If we choose product 0 and 3: min(max(3,2),max(3,4),max(2,3),max(4,2)) = 3

        If we choose product 1 and 2: min(max(4,2),max(3,3),max(4,2),max(2,4)) = 3

        If we choose product 1 and 3: min(max(4,2),max(3,4),max(4,3),max(2,2)) = 2

        If we choose product 2 and 3: min(max(2,2),max(3,4),max(2,3),max(4,2)) = 2

      
      
        Output = max(3,2,3,3,2,2) = 3

Constraints:

2 <= n <= m <= 10^5
0 <= ratings[i][j] <= 10^9
These constraints are based on memory; they might not be correct