590. Dream Team Output
A robotics club has n engineers. Engineer i assembles speed[i] parts per hour and works with an efficiency rating of efficiency[i]. The club forms a team of at most k engineers (at least one). The output of a team is the sum of its members' speeds multiplied by the smallest efficiency rating among its members.
Find the largest output any team can achieve. The true value can be huge, so compare candidates by their true values and only then return the best one modulo 1000000007 (10^9 + 7). The intended solution runs in O(n log n) time and O(n) space.
Example 1
- Input:
- n = 4speed = [2,8,3,5]efficiency = [7,2,9,4]k = 2
- Output:
- 35
- Explanation:
The engineers with speeds 2 and 3 (efficiencies 7 and 9) give (2 + 3) * 7 = 35, which beats every other team of up to two.
Example 2
- Input:
- n = 3speed = [5,5,5]efficiency = [3,3,3]k = 3
- Output:
- 45
- Explanation:
Everyone is equally efficient, so the whole team of three gives (5 + 5 + 5) * 3 = 45.
Example 3
- Input:
- n = 2speed = [100000,100000]efficiency = [100000000,100000000]k = 2
- Output:
- 999860007
- Explanation:
The true output is 200000 * 100000000 = 2 * 10^13, and its remainder modulo 1000000007 is returned.
Constraints
- 1 ≤ k ≤ n ≤ 105
- speed.length == efficiency.length == n
- 1 ≤ speed[i] ≤ 105
- 1 ≤ efficiency[i] ≤ 108
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)