DSA Factory
Free Mixed sets lessonsMixed sets · Stage 3 · Set 4 · Step 2

Pick the best team

Choose at most k workers to maximise the total speed times the lowest efficiency in the team, by going through workers from most to least efficient and keeping the fastest k in a heap. About 22 minutes.

Fix the minimum first

A team scores its total speed multiplied by its lowest efficiency. Two things vary at once, which is hard. Remove one: decide the lowest efficiency first.

Sort the workers from the highest efficiency to the lowest and go through them in that order. When you reach a worker, every worker seen so far is at least as efficient, so this worker's efficiency is the lowest the team can have if it includes them.

Sort by efficiency, highest first.
Current worker: sets the team's minimum.
In code
pairs = sorted(zip(eff, speed),
               reverse=True)
Speeds 4, 2, 6, 3, 1 and efficiencies 3, 7, 2, 5, 9, with k = 2. Workers by efficiency: 9, 7, 5, 3, 2.
1
0
2
1
3
2
4
3
6
4
i

Worker with efficiency 9 and speed 1. Team speed 1 times 9 = 9.

Move 1 of 3

The fastest k so far

For a fixed minimum, the best team takes the fastest workers among those seen, at most k of them. Keep their speeds in a min-heap with a running total. When the heap grows past k, drop the slowest, which is on top.

After each worker, the score is the running total times the current efficiency. The answer is the largest score over all steps. A team of fewer than k workers is fine, as the heap simply stays smaller.

Heap: speeds of the kept workers, slowest on top.
Score: total speed times the current efficiency.
In code
heapq.heappush(heap, spd)
total += spd
Quick check

Why is the current worker's efficiency the team's minimum?

  1. AAll earlier workers, the only ones considered, are at least as efficient
  2. BIt is the slowest worker
  3. CIt is the first worker
Show the answer

All earlier workers, the only ones considered, are at least as efficient. Workers are processed from the highest efficiency to the lowest.

Your problem

Maximum performance of a team

There are n engineers numbered 0 to n − 1. You are given two arrays speed and efficiency, where speed[i] and efficiency[i] describe engineer i, and an integer k. Choose at most k engineers to form a team. The performance of a team is the sum of its engineers' speeds multiplied by the minimum efficiency among them. Return the maximum possible performance.

Example
speed = [2, 10, 3, 1, 5, 8], efficiency = [5, 4, 3, 9, 7, 2], k = 2 → 60

1 ≤ k ≤ n ≤ 10,000 · 1 ≤ speed[i], efficiency[i] ≤ 100,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve