最大的团队表现值

标签: 贪心 数组 排序 堆（优先队列）

难度: 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（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=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 。

示例 3：

输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
输出：72

提示：

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

Submission

运行时间: 102 ms

内存: 36.4 MB

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        h = []
        total = 0
        ans = 0
        for s, e in sorted(zip(speed, efficiency), key = lambda x: -x[1]):
            heappush(h, s)
            total += s
            if len(h) > k:
                total -= heappop(h)
            ans = max(ans, total * e)
        return ans % 1000000007

Explain

题解的核心思想是首先根据工程师的效率从高到低排序，然后依次尝试每位工程师作为当前团队中效率最低的工程师的情况。利用最小堆来维护当前团队中的速度值，确保总是包含速度最大的工程师们。如果团队成员数超过 k 时，从堆中移除速度最小的工程师。这样，在每次迭代中，都计算使用当前效率和团队总速度的乘积，从而找到最大的团队表现值。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        h = []  # 最小堆，用于维持当前团队中的速度
        total = 0  # 当前团队的速度总和
        ans = 0  # 记录最大的团队表现值
        # 对工程师按照效率从高到低排序
        for s, e in sorted(zip(speed, efficiency), key = lambda x: -x[1]):
            heappush(h, s)  # 将当前工程师的速度添加到堆中
            total += s  # 更新速度总和
            if len(h) > k:  # 如果团队人数超过 k，需要移除速度最小的工程师
                total -= heappop(h)  # 更新总速度
            ans = max(ans, total * e)  # 计算当前团队的表现值，并更新最大表现值
        return ans % 1000000007  # 返回结果，对大数取模

Explore

按照效率从高到低排序并依次尝试每位工程师作为团队中效率最低的工程师是因为团队的表现值是由当前效率最低的工程师的效率与团队总速度的乘积决定的。若只选取效率最高的几位工程师，可能会忽略一些速度较高的工程师，导致团队的总速度不是最大。通过从高到低排序，可以确保在考虑每位工程师作为效率最低成员时，团队的其他成员的效率至少与他相同或更高，从而探索更多可能的最大团队表现值组合。

最小堆用于维持团队中速度最大的工程师们，以确保团队速度尽可能大。当团队成员数超过k时，移除速度最小的工程师是为了控制团队规模并尝试寻找一个速度更大的组合。即便移除了速度最小的工程师，由于我们是基于当前效率最低的工程师遍历的，总是有机会通过尝试其他的工程师组合来找到可能的最大团队表现值。

移除堆中的最小元素确实会导致总速度降低，但这是为了保持团队的规模不超过k，同时允许其他可能具有更高速度的工程师加入团队。这种方法不保证每一步都是局部最优解，但它是必要的以维持团队规模，并通过全局探索来尝试找到全局最优解。

因为团队的表现值是由当前团队中效率最低的工程师的效率和团队总速度决定的。在每次迭代中，团队的组成可能会发生变化（特别是速度和效率的变化），因此每次循环时更新最大表现值可以确保我们不会错过任何可能产生更高表现值的团队配置。若只在循环结束后计算一次，可能会丢失中途产生的最大值。