Skip to content

3961. Maximize Sum of Device Ratings

SourceWeekly Contest 506 Q3DifficultyMediumRating1879

Description

You are given a 2D integer array units of size m × n where units[i][j] represents the capacity of the jth unit in the ith device. Each device contains exactly n units.

The rating of a device is the minimum capacity among all its units.

You may perform the following operation any number of times (including zero):

  • Choose a device i that has not been used as a source before.
  • Remove exactly one unit from device i and add it to any different device.
  • Then mark device i as used, so it cannot be chosen again as a source.

Return the maximum possible sum of the ratings of all devices after any number of such operations.

Note:

  • Devices can receive units from multiple devices, regardless of whether they have been selected.
  • The rating of an empty device is 0.

 

Example 1:

Input: units = [[1,3],[2,2]]

Output: 4

Explanation:

  • ​​​​​​​​​​​​​​Select device i = 0 and transfer units[0][0] = 1 to device i = 1.
  • After the transfer, the ratings are:
    • Device 0 = [3]: rating[0] = 3
    • Device 1 = [2, 2, 1]: rating[1] = 1
  • Thus, the sum of ratings is 3 + 1 = 4.

Example 2:

Input: units = [[1,2,3],[4,5,6]]

Output: 6

Explanation:

  • Select device i = 1 and transfer units[1][0] = 4 to device i = 0.
  • After the transfer, the ratings are:
    • Device 0 = [1, 2, 3, 4]: rating[0] = 1
    • Device 1 = [5, 6]: rating[1] = 5
  • Thus, the sum of ratings is 1 + 5 = 6.

Example 3:

Input: units = [[5,5,5],[1,1,1]]

Output: 6

Explanation:

  • No transfers increase the sum of ratings. Thus, the sum of ratings is 5 + 1 = 6.

 

Constraints:

  • 1 <= m == units.length <= 105
  • 1 <= n == units[i].length <= 105
  • m * n <= 2 * 105
  • 1 <= units[i][j] <= 105

Solutions

Solution 1: Greedy

Thinking

A device’s rating is the smallest unit it keeps. Moving someone’s minimum onto another device can only replace the receiver’s second-smallest. When \(n=1\) nothing can move, so the answer is the sum of minima.

For \(n\ge 2\) each device keeps at least two units: sort each row and start from the sum of second-smallest values. The one useful adjustment merges the global minimum into the device whose second-smallest is tiniest, replacing that second-smallest.

The closed form is \(\sum x[1]-(mn_2-mn)\).

Adding a unit to a device can only decrease or keep its rating unchanged. Therefore, if \(n = 1\), we can directly return the sum of all device ratings.

Otherwise, we sort the units of each device in ascending order, take the smallest unit from each device, and concentrate them into one device with rating \(\textit{mn}\). If we concentrate them into device \(i\), the rating of device \(i\) changes from the second smallest value \(\textit{mn2}\) to \(\textit{mn}\), so the total rating decreases by \(\textit{mn2} - \textit{mn}\). To maximize the total rating, we should choose the device with the smallest decrease, i.e., the device with the smallest \(\textit{mn2}\).

The time complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of devices and the number of units per device, respectively. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxRatings(self, units: List[List[int]]) -> int:
        n = len(units[0])
        if n == 1:
            return sum(x[0] for x in units)

        ans = 0
        mn = mn2 = inf
        for x in units:
            x.sort()
            ans += x[1]
            mn2 = min(mn2, x[1])
            mn = min(mn, x[0])
        ans -= mn2 - mn
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public long maxRatings(int[][] units) {
        int n = units[0].length;
        if (n == 1) {
            long ans = 0;
            for (int[] x : units) {
                ans += x[0];
            }
            return ans;
        }

        long ans = 0;
        int mn = Integer.MAX_VALUE;
        int mn2 = Integer.MAX_VALUE;

        for (int[] x : units) {
            Arrays.sort(x);
            ans += x[1];
            mn2 = Math.min(mn2, x[1]);
            mn = Math.min(mn, x[0]);
        }

        ans -= (mn2 - mn);

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    long long maxRatings(vector<vector<int>>& units) {
        int n = units[0].size();
        if (n == 1) {
            long long ans = 0;
            for (auto& x : units) {
                ans += x[0];
            }
            return ans;
        }

        long long ans = 0;
        int mn = INT_MAX;
        int mn2 = INT_MAX;

        for (auto& x : units) {
            sort(x.begin(), x.end());
            ans += x[1];
            mn2 = min(mn2, x[1]);
            mn = min(mn, x[0]);
        }

        return ans - (mn2 - mn);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func maxRatings(units [][]int) int64 {
    n := len(units[0])
    if n == 1 {
        var ans int64
        for _, x := range units {
            ans += int64(x[0])
        }
        return ans
    }

    var ans int64
    mn, mn2 := int(^uint(0)>>1), int(^uint(0)>>1)

    for _, x := range units {
        sort.Ints(x)
        ans += int64(x[1])
        if x[1] < mn2 {
            mn2 = x[1]
        }
        if x[0] < mn {
            mn = x[0]
        }
    }

    return ans - int64(mn2-mn)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function maxRatings(units: number[][]): number {
    const n = units[0].length;

    if (n === 1) {
        let ans = 0;
        for (const x of units) {
            ans += x[0];
        }
        return ans;
    }

    let ans = 0;
    let mn = Infinity;
    let mn2 = Infinity;

    for (const x of units) {
        x.sort((a, b) => a - b);
        ans += x[1];
        mn2 = Math.min(mn2, x[1]);
        mn = Math.min(mn, x[0]);
    }

    return ans - (mn2 - mn);
}

Comments