1383. Maximum Performance of a Team

Problem

Tags: Array, Greedy, Sorting, Heap (Priority Queue)

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 i^th 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

Code

CPP

// 1383. Maximum Performance of a Team (4/14/53398)
// Runtime: 72 ms (93.75%) Memory: 36.90 MB (50.78%) 

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        static const int MOD = 1e9 + 7;
        uint64_t result = 0, s_sum = 0;
        vector<pair<int, int>> engineers;
        for (int i = 0; i < speed.size(); ++i) {
            engineers.emplace_back(efficiency[i], speed[i]);
        }
        sort(engineers.begin(), engineers.end(), greater<pair<int, int>>());
        priority_queue<int, vector<int>, greater<int>> min_heap;
        for (const auto& [e, s] : engineers) {
            s_sum += s;
            min_heap.emplace(s);
            if (min_heap.size() > k) {
                s_sum -= min_heap.top(); min_heap.pop();
            }
            result = max(result, s_sum * e);
        }
        return result % MOD;
    }
};

JS

// 1383. Maximum Performance of a Team (11/2/53404)
// Runtime: 484 ms (0.00%) Memory: 69.29 MB (62.50%) 

/**
 * @param {number} n
 * @param {number[]} speed
 * @param {number[]} efficiency
 * @param {number} k
 * @return {number}
 */
var maxPerformance = function(n, speed, efficiency, k) {
    // 把 engineers 依照 efficiency 遞減排序
    let engineers = [];
    for(let i = 0; i < n; i++) {
        engineers.push({ speed: speed[i], efficiency: efficiency[i] });
    }
    engineers.sort((a,b) => b.efficiency - a.efficiency);
    
    let highest_speeds = new MinPriorityQueue();
    
    let max_performance = BigInt(0), team_speed = 0;
    for(let i = 0; i < n; i++) {
        highest_speeds.enqueue(engineers[i].speed);
        team_speed += engineers[i].speed;
        if (highest_speeds.size() > k) {
            team_speed -= highest_speeds.dequeue().element;
        }
        
        let performance = BigInt(engineers[i].efficiency) * BigInt(team_speed);
        max_performance = performance > max_performance ? performance : max_performance;
    }
    
    return max_performance % BigInt(1e9 + 7);
};