# Maximum Performance of a Team
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-performance-of-a-team)
Canonical: https://scaleengineer.com/dsa/problems/maximum-performance-of-a-team
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [Citrix](https://scaleengineer.com/companies/citrix)
---
## Problem
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 its engineers' speeds multiplied by the minimum efficiency among its engineers.

Return _the maximum performance of this team_. Since the answer can be a huge number, return it **modulo** `109 + 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 <= 105`
* `speed.length == n`
* `efficiency.length == n`
* `1 <= speed[i] <= 105`
* `1 <= efficiency[i] <= 108`

# Approaches
## Brute Force by Fixing Minimum Efficiency
This approach iterates through every engineer, considering each one as the member with the minimum efficiency in a potential team. For each chosen minimum efficiency `E`, it finds the best possible team by gathering all engineers with efficiency greater than or equal to `E` and picking the `k` fastest among them.
**Time:** O(N^2 * logN). The outer loop runs `N` times. Inside, we iterate `N` times to find eligible engineers, and then sort a list of up to `N` elements, which takes `O(N log N)`. This dominates the inner loop, leading to `O(N * (N + N log N)) = O(N^2 log N)`. · **Space:** O(N). In each iteration of the outer loop, we create a list `eligibleSpeeds` which can store up to `N` speeds.
**Pros:** Conceptually simpler than the optimal approach.; Correctly identifies the structure of the problem (fixing minimum efficiency).
**Cons:** Too slow for the given constraints (`N <= 10^5`), will result in a "Time Limit Exceeded" error.; Repeatedly re-calculates and re-sorts lists of speeds, which is highly inefficient.
### Explanation
The core idea is that the minimum efficiency of an optimal team must be the efficiency of one of its members. We can iterate through each engineer `i` and fix their efficiency `efficiency[i]` as the minimum efficiency for a candidate team. For a fixed minimum efficiency `E = efficiency[i]`, any other engineer `j` in the team must have `efficiency[j] >= E`. To maximize the performance `(sum of speeds) * E`, we need to maximize the `sum of speeds`. This means we should select up to `k` engineers from the pool of those with `efficiency >= E` who have the highest speeds. After calculating the performance for this team, we update our overall maximum. By repeating this for every engineer, we ensure we have checked all possibilities for the minimum efficiency and found the global maximum performance.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        long maxPerformance = 0;
        long MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            int minEfficiency = efficiency[i];
            List<Integer> eligibleSpeeds = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (efficiency[j] >= minEfficiency) {
                    eligibleSpeeds.add(speed[j]);
                }
            }

            Collections.sort(eligibleSpeeds, Collections.reverseOrder());

            long currentSpeedSum = 0;
            for (int l = 0; l < Math.min(k, eligibleSpeeds.size()); l++) {
                currentSpeedSum += eligibleSpeeds.get(l);
            }

            maxPerformance = Math.max(maxPerformance, currentSpeedSum * minEfficiency);
        }

        return (int) (maxPerformance % MOD);
    }
}
```
### Algorithm
*   Initialize `max_performance = 0`.
*   For each engineer `i` from `0` to `n-1`:
    *   Set `min_eff = efficiency[i]`.
    *   Create a list `eligible_speeds`.
    *   For each engineer `j` from `0` to `n-1`:
        *   If `efficiency[j] >= min_eff`, add `speed[j]` to `eligible_speeds`.
    *   Sort `eligible_speeds` in descending order.
    *   Initialize `current_speed_sum = 0`.
    *   Iterate through the first `min(k, eligible_speeds.size())` elements of `eligible_speeds` and add them to `current_speed_sum`.
    *   Calculate `current_performance = current_speed_sum * min_eff`.
    *   Update `max_performance = max(max_performance, current_performance)`.
*   Return `max_performance` modulo `10^9 + 7`.

## Greedy Approach with Priority Queue
This is an efficient approach that avoids redundant computations by processing engineers in a specific order. By sorting engineers by their efficiency in descending order, we can iterate through them and maintain a running team of size `k` with the highest speeds encountered so far. A min-priority queue is used to efficiently manage this team.
**Time:** O(N log N). Sorting the engineers takes `O(N log N)`. The loop runs `N` times, and each heap operation (add/poll) takes `O(log K)`. So the loop takes `O(N log K)`. The total complexity is dominated by sorting, resulting in `O(N log N)`. · **Space:** O(N). We use an array of size `N` to store the engineer pairs. The priority queue stores at most `K` elements. So, the space complexity is `O(N + K) = O(N)`.
**Pros:** Highly efficient and passes the given constraints.; Optimal solution for this problem.; Clever use of sorting and a priority queue to avoid re-computation.
**Cons:** The logic is more complex to understand compared to the brute-force approach.; Requires careful handling of data structures (sorting pairs, using a priority queue).
### Explanation
The key insight is that if we consider engineers in decreasing order of their efficiency, then for any engineer we are currently at, their efficiency is the minimum among all engineers we have seen so far. This allows us to fix the `min_efficiency` term of the performance formula and focus on maximizing the `sum_of_speeds`.

The algorithm first pairs up efficiencies and speeds and sorts these pairs by efficiency in descending order. Then, it iterates through the sorted engineers. A min-priority queue (min-heap) is used to maintain the speeds of the current team members. For each engineer, we add their speed to the heap and a running sum. If the team size (heap size) exceeds `k`, we remove the engineer with the smallest speed (the root of the min-heap) to maintain the team size and keep the sum of speeds as high as possible. At each step, we calculate a potential maximum performance by multiplying the current sum of speeds by the current engineer's efficiency (which is the minimum in the current pool). We keep track of the highest performance value seen during the iteration.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

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[]{efficiency[i], speed[i]};
        }

        // Sort engineers by efficiency in descending order
        Arrays.sort(engineers, (a, b) -> b[0] - a[0]);

        // Min-heap to maintain the k largest speeds
        PriorityQueue<Integer> speedHeap = new PriorityQueue<>(k, (a, b) -> a - b);
        
        long currentSpeedSum = 0;
        long maxPerformance = 0;
        long MOD = 1_000_000_007;

        for (int[] engineer : engineers) {
            int currentEfficiency = engineer[0];
            int currentSpeed = engineer[1];

            // Add current engineer's speed to the team
            speedHeap.add(currentSpeed);
            currentSpeedSum += currentSpeed;

            // If team size exceeds k, remove the one with the lowest speed
            if (speedHeap.size() > k) {
                currentSpeedSum -= speedHeap.poll();
            }

            // Calculate performance with the current team.
            // The minimum efficiency is the current engineer's efficiency
            // because we sorted by efficiency in descending order.
            maxPerformance = Math.max(maxPerformance, currentSpeedSum * currentEfficiency);
        }

        return (int) (maxPerformance % MOD);
    }
}
```
### Algorithm
*   Create a 2D array or a list of objects to store `(efficiency, speed)` pairs for each engineer.
*   Sort these pairs in descending order of efficiency.
*   Initialize a min-priority queue `speed_heap`.
*   Initialize `speed_sum = 0` and `max_performance = 0` (using long to prevent overflow).
*   For each engineer `(E, S)` in the sorted list:
    *   Add the current speed `S` to `speed_heap`.
    *   Add `S` to `speed_sum`.
    *   If `speed_heap.size() > k`:
        *   Remove the minimum speed from the heap: `min_speed = speed_heap.poll()`.
        *   Subtract `min_speed` from `speed_sum`.
    *   Calculate `current_performance = speed_sum * E`.
    *   Update `max_performance = max(max_performance, current_performance)`.
*   Return `max_performance % (10^9 + 7)`.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
    int[][] t = new int[n][2];
    for (int i = 0; i < n; ++i) {
      t[i] = new int[]{speed[i], efficiency[i]};
    }
    Arrays.sort(t, (a, b)->b[1] - a[1]);
    PriorityQueue<Integer> q = new PriorityQueue<>();
    long tot = 0;
    long ans = 0;
    for (var x : t) {
      int s = x[0], e = x[1];
      tot += s;
      ans = Math.max(ans, tot * e);
      q.offer(s);
      if (q.size() == k) {
        tot -= q.poll();
      }
    }
    return (int)(ans % MOD);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxPerformance(int n, vector<int> &speed, vector<int> &efficiency,
                     int k) {
    vector<pair<int, int>> t(n);
    for (int i = 0; i < n; ++i)
      t[i] = {-efficiency[i], speed[i]};
    sort(t.begin(), t.end());
    priority_queue<int, vector<int>, greater<int>> q;
    long long ans = 0, tot = 0;
    int mod = 1e9 + 7;
    for (auto &x : t) {
      int s = x.second, e = -x.first;
      tot += s;
      ans = max(ans, tot * e);
      q.push(s);
      if (q.size() == k) {
        tot -= q.top();
        q.pop();
      }
    }
    return (int)(ans % mod);
  }
};

```

### Python

```python
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

```