Best Crew Score
MediumHeap / Priority Queue
Problem
An expedition picks a crew of exactly k people from n candidates. Candidate i has skill[i] and stamina[i]. A crew's score is the sum of its members' skills multiplied by the lowest stamina among its members, because the whole crew moves at the pace of its least enduring member.
Return the maximum possible score.
Example 1
- Input:
- skill = [3, 1, 4, 2], stamina = [2, 5, 3, 4], k = 2
- Output:
- 18
Candidates 2 and 3: (4 + 2) × min(3, 4) = 18. Candidates 1 and 3 give (1 + 2) × 4 = 12, candidates 0 and 2 give 7 × 2 = 14.
Example 2
- Input:
- skill = [5, 5, 5], stamina = [1, 2, 3], k = 3
- Output:
- 15
Constraints
- 1 ≤ k ≤ n ≤ 10^5
- 0 ≤ skill[i] ≤ 10^5
- 1 ≤ stamina[i] ≤ 10^5
Hint
Show the first hint
Fix who has the lowest stamina in the crew. What do you want from the other k - 1 members then?
Walkthrough
How to approach it
01Clarify before coding
- Exactly k members? Yes.
- Can skills be 0? Yes; stamina is at least 1.
- Can the score overflow 32 bits? Up to 10^5 · 10^5 · 10^5 = 10^15, fine in Python and below 2^53 in JavaScript.
02Brute force
Enumerate every crew of size k and compute its score.
Cost: C(n, k) crews: exponential. Fixing the minimum-stamina member and sorting the rest each time 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.