How do I approach the Maximum Performance of a Team problem?

Use a greedy approach by sorting engineers by efficiency and tracking the highest speeds using a min-heap.

What is the time complexity of the Maximum Performance of a Team problem?

The time complexity is O(n log n), dominated by the sorting step and heap operations.

How do I ensure the team performance is maximized in this problem?

Maximize the team performance by always selecting engineers with the highest efficiencies and speeds, ensuring the sum of speeds is optimal for the minimum efficiency.

What is the primary pattern used to solve this problem?

This problem uses a greedy choice combined with invariant validation, focusing on maximizing team performance based on sorted efficiencies and a heap for speed tracking.

What is the role of the min-heap in the solution?

The min-heap helps track the sum of the selected engineers' speeds, ensuring that the k engineers with the highest total speed are selected at each step.

#1383

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

最大的团队表现值

给定两个整数 n 和 k ，以及两个长度为 n 的整数数组 speed 和 efficiency 。现有 n 名工程师，编号从 1 到 n 。其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。从这 n 名工程师中最多选择 k 名不同的工程师，使其组成的团…

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

题目描述

给定两个整数 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

lightbulb

解题思路

方法一：贪心 + 优先队列（小根堆）

本题是求“速度和”与“效率最小值”乘积的最大值。变量有两个，我们可以从大到小枚举 efficiency[i] 作为效率最小值，在所有效率大于等于 efficiency[i] 的工程师中选取不超过 $k-1$ 个，让他们速度和最大。

时间复杂度 $O(n\log n)$ 。

相似题目：

857. 雇佣 K 名工人的最低成本

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests understanding of greedy algorithms and invariant maintenance.
question_mark
Assesses ability to optimize performance while handling large inputs.
question_mark
Evaluates proficiency with heap data structures for efficient selection and tracking.

warning

常见陷阱

外企场景

error
Not maintaining the correct number of engineers in the heap, which can lead to incorrect performance calculations.
error
Failing to sort the engineers by efficiency in decreasing order, which could lead to suboptimal selections.
error
Overcomplicating the problem by not recognizing the importance of a greedy choice in maximizing performance.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem could involve different performance formulas, such as weighted averages or more complex functions of speed and efficiency.
arrow_right_alt
Instead of k engineers, you might need to select the best team given a fixed budget or constraints on individual engineer costs.
arrow_right_alt
Consider an extended version where the engineers have different skill levels or other attributes affecting the performance calculation.

help

常见问题

外企场景

继续练习

#1353 最多可以参加的会议数目 #1338 数组大小减半 #1648 销售价值减少的颜色球