Solution: Maximum Performance of a Team
Tags: algorithms, javascript, java, python
Published: 2021-06-05 10:01:26

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/maximum-performance-of-a-team/discuss/1252316).*

---

#### [Leetcode Problem #1383 (*Hard*): Maximum Performance of a Team](https://leetcode.com/problems/maximum-performance-of-a-team/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

---

#### ***Examples:***
>
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`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The trick to this problem, like many best product of **x** and **y** problems, is to find a way to iterate through one of the values in order, then evaluate the other value for each combination and take the **best** result. If we sort the engineers by **efficiency**, we can iterate downward through the engineers while evaluating the combined speed (**totalSpeed**) of the ideal group.

Since the index numbers between **speed** and **efficiency** correspond to each other, we shouldn't just sort **efficiency**, however. Instead, we can create another array of arrays (**ord**) with both stats combined into one array, then sort it based on the efficiency.

As we iterate through the engineers in **ord** order and add them to the available pool, we know that all the engineers so far are at or higher than **minEff**, so we're free to only choose the **k** fastest engineers for our group. To keep track of the sorted order of speeds of the engineers in our available pool, we can use a **min priority queue** (**sppq**) or **min heap** (**spheap**) structure. This way, we can eliminate the slowest engineer from our pool every time we add an engineer over the **k** limit. At each stop, we should also find the product of **totalSpeed** and the current minimum efficiency and update the **best** result if necessary.

It's important to note that the instructions say "at most" **k** engineers, so we should start keeping track of **best** right away. Also, we should remember to **modulo 1e9+7** before we **return best**.

 - _**Time Complexity: O(N * log(N))** where **N** is the length of **speed** or **efficiency**, for the sorting of **ord** and for the priority queue / heap_
 - _**Space Complexity: O(N)** for **ord** and **sppq** / **spheap**_

---

#### ***Implementation:***

The Javascript code would be even faster with a custom **heap** implementation. The **MinPriorityQueue()** npm is easier to use, but not as efficient.

Javascript is faster by passing only the index reference into the priority queue, rather than combining both stats into an array before storage.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var maxPerformance = function(n, speed, efficiency, k) {
    let ord = Array.from({length: n}, (_,i) => i)
    ord.sort((a,b) => efficiency[b] - efficiency[a])
    let sppq = new MinPriorityQueue(),
        totalSpeed = 0n, best = 0n
    for (let eng of ord) {
        sppq.enqueue(speed[eng])
        if (sppq.size() <= k) totalSpeed += BigInt(speed[eng])
        else totalSpeed += BigInt(speed[eng] - sppq.dequeue().element)
        let res = totalSpeed * BigInt(efficiency[eng])
        if (res > best) best = res
    }
    return best % 1000000007n
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        ord = sorted(zip(efficiency, speed), reverse=True)
        spheap, totalSpeed, best = [], 0, 0
        for eff, spd in ord:
            heappush(spheap, spd)
            if len(spheap) <= k: totalSpeed += spd
            else: totalSpeed += spd - heappop(spheap)
            best = max(best, totalSpeed * eff)
        return best % 1000000007
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        int[][] ord = new int[n][2];
        for (int i = 0; i < n; i++)
            ord[i] = new int[] {efficiency[i], speed[i]};
        Arrays.sort(ord, (a, b) -> Integer.compare(b[0], a[0]));
        PriorityQueue<Integer> sppq = new PriorityQueue<>();
        long totalSpeed = 0, best = 0;
        for (int[] pair : ord) {
            int spd = pair[1];
            sppq.add(spd);
            if (sppq.size() <= k) totalSpeed += spd;
            else totalSpeed += spd - sppq.poll();
            best = Math.max(best, totalSpeed * pair[0]);
        }
        return (int)(best % 1000000007);
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        vector<pair<int, int>> ord;
        for (int i = 0; i < n; i++)
            ord.push_back({efficiency[i], speed[i]});
        sort(ord.rbegin(), ord.rend());
        priority_queue<int> sppq;
        long totalSpeed = 0, best = 0;
        for (auto& p : ord) {
            int spd = p.second;
            sppq.push(-spd);
            if (sppq.size() <= k) totalSpeed += spd;
            else {
                totalSpeed += spd + sppq.top();
                sppq.pop();
            }
            best = max(best, totalSpeed * p.first);
        }
        return best % 1000000007;
    }
};
```