1383. Maximum Performance of a Team - kumaeki/LeetCode GitHub Wiki

1383. Maximum Performance of a Team

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

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

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 10^9 + 7.

Example 1:

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.

Example 2:

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.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints:

  • 1 <= k <= n <= 10^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^8

解法1

每次计算时 efficiency都是取最小的, 所以可以把efficiency来排序, 然后去找speed最大的k个值.

class Solution {
    public int maxPerformance(int n, int[] speed, int[] eff, int k) {
        long res = 0, mod = (long)(1e9 + 7);
        long sum = 0;
        sort(speed, eff, 0, n - 1);
        PriorityQueue<Integer> que = new PriorityQueue<Integer>();
        for(int i = 0; i < n; i++){
            int s = speed[i], e = eff[i];
            while(que.size() == k)
                sum -= que.poll();
            que.offer(s);
            sum += s;
            res = Math.max(res, sum * e);
        }
        return (int)(res % mod);
    }
    // 快速排序,按照eff的降序来排序speed和eff
    private void sort(int[] speed, int[] eff, int left, int right) {
        if (left >= right)
            return;

        int temp = eff[left];
        int index = left + 1;
        for (int i = left + 1; i <= right; i++) {
            if (eff[i] >= temp) {
                swap(eff, i, index);
                swap(speed, i, index);
                index++;
            }
        }
        index--;
        swap(eff, index, left);
        swap(speed, index, left);

        sort(speed, eff, left, index - 1);
        sort(speed, eff, index + 1, right);
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

解法2

和解法1完全一样的思路, 不过可以写成更好懂的方式.

不过因为定义了额外的二维数组, 会稍微慢一些.

public class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        int[][] engineers = new int[n][2];
        for (int i = 0; i < n; i++)
            engineers[i] = new int[] { speed[i], efficiency[i] };

        Arrays.sort(engineers, (e1, e2) -> (e2[1] - e1[1]));

        long mod = (long) (1e9 + 7);
        long res = 0, totalSpeed = 0;
        PriorityQueue<Integer> que = new PriorityQueue<Integer>(k);
        for (int[] eng : engineers) {
            if (que.size() == k)
                totalSpeed -= que.poll();
            que.offer(eng[0]);
            totalSpeed += eng[0];
            res = Math.max(res, totalSpeed * eng[1]);
        }

        return (int) (res % mod);
    }
}
⚠️ **GitHub.com Fallback** ⚠️