Strongest Project Team
HardGreedy
Problem
A manager picks a project team of at most teamSize engineers out of n. Engineer i has speeds[i] and efficiencies[i]. A team's output is the sum of its members' speeds multiplied by the lowest efficiency in the team.
Return the largest possible output of a non-empty team.
Example 1
- Input:
- speeds = [4, 9, 2, 7], efficiencies = [6, 3, 8, 5], teamSize = 2
- Output:
- 55
Engineers with speed 4 and 7: (4 + 7) × min(6, 5) = 55.
Example 2
- Input:
- speeds = [4, 9, 2, 7], efficiencies = [6, 3, 8, 5], teamSize = 4
- Output:
- 66
Engineers with speeds 4, 2, 7: (4 + 2 + 7) × 5 = 65 is beaten by all four: (4 + 9 + 2 + 7) × 3 = 66.
Constraints
- 1 ≤ teamSize ≤ n ≤ 10^4
- 1 ≤ speeds[i], efficiencies[i] ≤ 10^4
Hint
Show the first hint
The output depends on one 'bottleneck' engineer: the one with the lowest efficiency. Try fixing who that is.
Walkthrough
How to approach it
01Clarify before coding
- Is a team of fewer than teamSize engineers allowed? Yes, at most teamSize.
- Does a single engineer form a valid team? Yes; output = speed × efficiency.
- How large can the result be? Up to 10^4 · 10^4 · 10^4 = 10^12, so use 64-bit integers (fine for Python and JS numbers).
02Brute force
Try every subset of at most teamSize engineers.
Cost: Exponential. Even 'fix the minimum, then pick the fastest' done naively is O(n² log n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.