Maximum Performance of a Team
Hard · Heap & Counting · Array · Greedy · Sorting · Heap (Priority Queue)
Problem
You have n engineers numbered 1 to n. Engineer i has speed speed[i] and efficiency efficiency[i]. Choose at most k engineers to form a team.
A team's performance is the sum of its members' speeds multiplied by the lowest efficiency among its members.
Return the largest performance any team can reach, modulo 10^9 + 7. Find the true maximum first and only then take the remainder: the remainders do not preserve order.
Examples
Input: n = 4, speed = [3,5,2,8], efficiency = [6,4,7,2], k = 2 Output: 32
Engineers 1 and 2 give (3 + 5) × min(6, 4) = 32. The fastest engineer (speed 8) has efficiency 2, which drags any team down.
Input: n = 3, speed = [1,1,1], efficiency = [9,9,9], k = 3 Output: 27
Taking all three gives (1 + 1 + 1) × 9 = 27.
Input: n = 3, speed = [2,10,3], efficiency = [5,4,3], k = 3 Output: 48
Engineers 1 and 2 give 12 × 4 = 48. Adding engineer 3 gives 15 × 3 = 45, which is less.
Constraints
- 1 <= k <= n <= 10^5
- len(speed) == len(efficiency) == n
- 1 <= speed[i] <= 10^5
- 1 <= efficiency[i] <= 10^8
Approaches
- Fix the least efficient member, take the fastest who qualify — time O(n² log n), space O(n)
Follow-up
The product reaches about 10^18. Which types hold it in Java, C++, Go and JavaScript? And what changes if the team must have exactly k members?
Related problems
Start free on Cariara · Coding problems · System design studio
