LeetCode 1383. Maximum Performance Of a Team

, , , , ,

Question

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Input: n = 3, speed = [2,8,2], efficiency = [2,7,1] k = 2
Output: 56
Explanation: 
We only need to choose the second worker.

Solution

以下主要参考lee215大佬的贪心解法。

首先，这里的计算方式为所有的速度之和乘以最小的效率值，即为sum(speed) * min(efficiency)。并且说定了最多选k个，其实达到最高的计算值只由一个人完成（如同例子3）。我们需要保持最大的有效值（efficiency），利用最小堆保持速度，当选中的worker超过k就poll出来。其实这里为啥可以用，目前我也是懵逼。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// sort: nlogn, pq: nlogk, space: O(2 * n)
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        int[][] data = new int[n][2];
        for (int i = 0; i < n; i++) {
            data[i] = new int[]{efficiency[i], speed[i]};
        }
        // 按照efficiency逆序
        Arrays.sort(data, (a,b) -> (b[0] - a[0]));
        // 按照speed 增序 
        PriorityQueue<Integer> pq = new PriorityQueue<>(k, (a, b) -> a - b);
        long res = 0, sum = 0;
        long MOD = (long) Math.pow(10, 9) + 7;
        for (int[] es : data) {
            pq.offer(es[1]);
            sum = (sum + es[1]);
            if (pq.size() > k) sum -= pq.poll();
            res = Math.max(res, (sum * es[0]));
        }
        return (int) (res % MOD);
    }