Hard

题目描述

给定两个整数 n 和 k，以及两个长度为 n 的整数数组 speed 和 efficiency。有 n 名工程师，编号从 1 到 n。speed[i] 和 efficiency[i] 分别表示第 i 名工程师的速度和效率。

从 n 名工程师中最多选择 k 名不同的工程师组成一个团队，使团队的工作效率最大。

团队的工作效率是其工程师速度之和乘以其工程师中最小效率值。

返回这个团队的最大工作效率。由于答案可能很大，请返回结果对 10^9 + 7 取余。

示例 1：

输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
输出：60
解释：
我们选择工程师 2（速度=10，效率=4）和工程师 5（速度=5，效率=7）来达到最大的团队工作效率。
即，performance = (10 + 5) * min(4, 7) = 60。

示例 2：

输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
输出：68
解释：
这与第一个示例相同，但 k = 3。我们可以选择工程师 1、工程师 2 和工程师 5 来获得团队的最大工作效率。
即，performance = (2 + 10 + 5) * min(5, 4, 7) = 68。

提示：

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

解题思路

解题思路

这是一道贪心算法结合优先队列的经典题目。核心思想是：对于固定的最小效率值，我们希望选择速度最大的工程师来最大化团队表现。

算法步骤：

  1. 排序策略：将所有工程师按效率从高到低排序。这样我们可以依次考虑每个工程师作为团队中效率最低的那个人。

  2. 贪心选择：当我们固定某个工程师的效率作为团队最小效率时，为了最大化团队表现，我们应该从效率不小于该值的工程师中选择速度最大的k-1个工程师。

  3. 优先队列优化：使用最小堆来维护当前团队中的工程师速度。当团队人数超过k时，移除速度最小的工程师。

  4. 遍历更新：从效率最高的工程师开始，依次将每个工程师加入团队，更新最大表现值。

这种方法的精妙之处在于，通过按效率排序，我们确保了在考虑第i个工程师时，前面所有工程师的效率都不小于第i个工程师，因此第i个工程师的效率就是当前团队的最小效率。

推荐解法：贪心 + 优先队列，时间复杂度O(n log n)，是最优解法。

代码实现

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        const long MOD = 1e9 + 7;
        
        // 将工程师按效率降序排列
        vector<pair<int, int>> engineers;
        for (int i = 0; i < n; i++) {
            engineers.push_back({efficiency[i], speed[i]});
        }
        sort(engineers.begin(), engineers.end(), greater<pair<int, int>>());
        
        // 使用最小堆维护当前团队中的速度
        priority_queue<int, vector<int>, greater<int>> speedHeap;
        long speedSum = 0;
        long maxPerf = 0;
        
        for (auto& engineer : engineers) {
            int eff = engineer.first;
            int spd = engineer.second;
            
            // 将当前工程师加入团队
            speedHeap.push(spd);
            speedSum += spd;
            
            // 如果团队人数超过k，移除速度最小的工程师
            if (speedHeap.size() > k) {
                speedSum -= speedHeap.top();
                speedHeap.pop();
            }
            
            // 更新最大表现
            maxPerf = max(maxPerf, speedSum * eff);
        }
        
        return maxPerf % MOD;
    }
};

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        import heapq
        
        MOD = 10**9 + 7
        
        # 将工程师按效率降序排列
        engineers = sorted(zip(efficiency, speed), reverse=True)
        
        # 使用最小堆维护当前团队中的速度
        speed_heap = []
        speed_sum = 0
        max_perf = 0
        
        for eff, spd in engineers:
            # 将当前工程师加入团队
            heapq.heappush(speed_heap, spd)
            speed_sum += spd
            
            # 如果团队人数超过k，移除速度最小的工程师
            if len(speed_heap) > k:
                speed_sum -= heapq.heappop(speed_heap)
            
            # 更新最大表现
            max_perf = max(max_perf, speed_sum * eff)
        
        return max_perf % MOD

public class Solution {
    public int MaxPerformance(int n, int[] speed, int[] efficiency, int k) {
        const long MOD = 1_000_000_007;
        
        // 将工程师按效率降序排列
        var engineers = new (int eff, int spd)[n];
        for (int i = 0; i < n; i++) {
            engineers[i] = (efficiency[i], speed[i]);
        }
        Array.Sort(engineers, (a, b) => b.eff.CompareTo(a.eff));
        
        // 使用最小堆维护当前团队中的速度
        var speedHeap = new PriorityQueue<int, int>();
        long speedSum = 0;
        long maxPerf = 0;
        
        foreach (var (eff, spd) in engineers) {
            // 将当前工程师加入团队
            speedHeap.Enqueue(spd, spd);
            speedSum += spd;
            
            // 如果团队人数超过k，移除速度最小的工程师
            if (speedHeap.Count > k) {
                speedSum -= speedHeap.Dequeue();
            }
            
            // 更新最大表现
            maxPerf = Math.Max(maxPerf, speedSum * eff);
        }
        
        return (int)(maxPerf % MOD);
    }
}

var maxPerformance = function(n, speed, efficiency, k) {
    const MOD = 1e9 + 7;
    
    // 将工程师按效率降序排列
    const engineers = [];
    for (let i = 0; i < n; i++) {
        engineers.push([efficiency[i], speed[i]]);
    }
    engineers.sort((a, b) => b[0] - a[0]);
    
    // 使用数组模拟最小堆维护当前团队中的速度
    const speedHeap = [];
    let speedSum = 0;
    let maxPerf = 0;
    
    for (const [eff, spd] of engineers) {
        // 将当前工程师加入团队
        speedHeap.push(spd);
        speedSum += spd;
        
        // 保持堆的性质（最小堆）
        speedHeap.sort((a, b) => a - b);
        
        // 如果团队人数超过k，移除速度最小的工程师
        if (speedHeap.length > k) {
            speedSum -= speedHeap.shift();
        }
        
        // 更新最大表现
        maxPerf = Math.max(maxPerf, speedSum * eff);
    }
    
    return maxPerf % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序O(n log n)和堆操作O(n log k)
空间复杂度O(n + k)存储工程师数组O(n)和优先队列O(k)

相关题目