Maximum Performance of a Team
You have n engineers. Engineer i has speedi and efficiencyi. You may pick at most k of them. The performance of a team is the sum of the speeds times the smallest efficiency in the team . Return the highest performance you can reach, given modulo 109 + 7 because the number can get very large. Sort the engineers from highest efficiency to lowest. Walking the sorted list, the engineer you are on is the weakest link of any team made from the ones seen so far , so their efficiency is the multiplier. All that is left is to make the speed total as big as possible, which means keeping the k fastest engineers. A min-heap of speeds does that: once it holds more than k speeds, drop the slowest one.
Constraints
- 1 ≤ n ≤ 105
- 1 ≤ k ≤ n
- 1 ≤ speedi ≤ 105
- 1 ≤ efficiencyi ≤ 108
Example
n = 6, speed = [2, 10, 3, 1, 5, 8], efficiency = [5, 4, 3, 9, 7, 2], k = 260Explanation Picking engineer 1 (speed 10, efficiency 4) and engineer 4 (speed 5, efficiency 7) gives speeds 10 + 5 = 15 and a smallest efficiency of 4, so the performance is 15 times 4 = 60. No other team of at most 2 does better.
In plain terms
- Heap
- A container that always knows its best item, where best means smallest or largest depending on how you set it up. Adding an item or taking the best item out costs about log n steps, and you never have to sort the whole collection.
- Backing array
- A heap is stored as one plain list. The item at position i keeps its parent at position (i - 1) / 2 rounded down, and its two children at positions 2i + 1 and 2i + 2. That is why every picture below is a row of numbered boxes.
- Min-heap
- A heap whose best item is the smallest one. Here it is used the other way round from usual: you pop the smallest speed in order to throw it away.
- Modulo
- The remainder after dividing. Taking the answer modulo 109 + 7 keeps it inside a normal number range, which is a common rule in these problems.
- At most k
- Smaller teams are allowed. The code records the best value seen after every engineer, so a team of 1 or 2 can win even when k is larger.
The row of boxes is the backing array of the min-heap of chosen speeds, walking engineers from highest efficiency down
Pair each engineer as efficiency and speed, then sort by efficiency from high to low.
What happens in this step
k = 2 sorted engineers = (9,1), (7,5), (5,2), (4,10), (3,3), (2,8) written as (efficiency, speed) heap is empty, speedSum = 0, best = 0
Steps to visualize
- Engineers are sorted by efficiency, highest first: (eff 9, speed 1), (7, 5), (5, 2), (4, 10), (3, 3), (2, 8).
- Each box is one slot of the list that stores the heap of speeds currently on the team. Slot 0 holds the slowest of them.
- For each engineer: add their speed, and if the team is now bigger than k, pop slot 0 to drop the slowest engineer.
- The current engineer always has the lowest efficiency so far, so their efficiency is the multiplier for this round.
- Keep the largest speedSum times efficiency seen at any point.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Pair each engineer as efficiency and speed, then sort by efficiency from high to low.
What happens in this step
k = 2 sorted engineers = (9,1), (7,5), (5,2), (4,10), (3,3), (2,8) written as (efficiency, speed) heap is empty, speedSum = 0, best = 0
Solution
function maxPerformance(n, speed, efficiency, k) {
const engineers = [];
for (let i = 0; i < n; i++) {
engineers.push([efficiency[i], speed[i]]);
}
engineers.sort((a, b) => b[0] - a[0]);
const speeds = new Heap((a, b) => a - b);
let speedSum = 0;
let best = 0;
for (const engineer of engineers) {
speeds.push(engineer[1]);
speedSum += engineer[1];
if (speeds.size() > k) {
speedSum -= speeds.pop();
}
best = Math.max(best, speedSum * engineer[0]);
}
return best % 1000000007;
}
class Heap {
constructor(compare) {
this.items = [];
this.compare = compare;
}
size() {
return this.items.length;
}
peek() {
return this.items[0];
}
push(value) {
this.items.push(value);
let child = this.items.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (this.compare(this.items[child], this.items[parent]) >= 0) break;
const swap = this.items[child];
this.items[child] = this.items[parent];
this.items[parent] = swap;
child = parent;
}
}
pop() {
const top = this.items[0];
const last = this.items.pop();
if (this.items.length > 0) {
this.items[0] = last;
let parent = 0;
while (true) {
const left = parent * 2 + 1;
const right = parent * 2 + 2;
let best = parent;
if (left < this.items.length && this.compare(this.items[left], this.items[best]) < 0) best = left;
if (right < this.items.length && this.compare(this.items[right], this.items[best]) < 0) best = right;
if (best === parent) break;
const swap = this.items[parent];
this.items[parent] = this.items[best];
this.items[best] = swap;
parent = best;
}
}
return top;
}
}- Time
- O(n log n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
n = 6, speed = [2, 10, 3, 1, 5, 8], efficiency = [5, 4, 3, 9, 7, 2], k = 2 | 60 | example from the docstring |
same engineers, k = 3 | 68 | a bigger team is allowed, so the answer improves |
same engineers, k = 4 | 72 | a larger team again, showing at most k rather than exactly k |
n = 1, speed = [5], efficiency = [4], k = 1 | 20 | smallest possible input |
n = 3, speed = [2, 8, 2], efficiency = [2, 7, 1], k = 2 | 56 | a team of one beats every team of two |
n = 2, speed = [1, 1], efficiency = [1, 1], k = 2 | 2 | duplicate speeds and efficiencies |