Last Updated: 8 Apr, 2021
Maximum Performance of a Team
Moderate
Asked in company
Ninja is forming a team of at most ‘K’ engineers out of the ‘N’ engineers. For each engineer, Ninja has his ‘SPEED’ and his ‘EFFICIENCY’. He wants to form the team so that the ‘performance’ of the team is maximal.
The ‘performance’ of the team is defined as the sum of the ‘SPEED’ of the engineers present in the team multiplied by the minimum ‘EFFICIENCY’ among the engineers in the same team. Since Ninja is busy with other work, he wants your help to solve this task.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains two positive integers, ‘N’, and ‘K’, denoting the total number of engineers and the maximum number of engineers in a team.
The second line of each test case contains ‘N’ space-separated integers, ‘SPEED[i]’, representing the ith engineer’s speed.
The third line of each test case contains ‘N’ space-separated integers, ‘EFFICIENCY[i]’, representing the ith engineer’s efficiency.
Output Format:
For each test case, print the ‘maximum performance’ of the team modulo ‘10^9 + 7’, as described in the problem statement.
Output for each test case will be printed in a separate line.
Note:
1. You do not need to print anything. It has already been taken care of. Just implement the given function.
2. Since the answer can be a big number, you have to return its modulo ‘10^9 + 7’.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^4
1 <= ‘K’ <= ‘N’
1 <= ‘SPEED[i]’, ‘EFFICIENCY[i]’ <= 10^4
SPEED.length == EFFICIENCY.length == N
Where ‘SPEED[i]’ is the speed of the i-th engineer, and ‘EFFICIENCY[i]’ is the efficiency of the i-th engineer.
Time Limit: 1 sec
Approaches
- The idea here is to do the sorting on the basis of efficiency and then use the min-heap to solve the problem.
- First, we create a 2-D array named 'ENGINEERS_DATA'[N][2], where the 1st element of the ith row is the speed[i], and the 2nd element of the i-th row is the 'EFFICIENCY'[i].
- Sort the array 'ENGINEERS_DATA' in decreasing order based on 'EFFICIENCY'.
- In each team, we take that engineer as the last engineer whose 'EFFICIENCY' is smallest among them who are already present in that team. In other words, if we took the ith engineer as the last engineer in our team, then we can only take the engineers whose 'EFFICIENCY' is greater than the ith one. As we have already sorted it based on the 'EFFICIENCY', so according to our sorted array these elements will lie in the front of the ith engineer.
- So to implement the above logic we can keep the priority queue named 'PQ' with the maximum size of ‘K’. When the queue size becomes K, and we want to push the new engineer, we can remove the one whose speed is lowest among those already in the 'PQ'.
- We create a min-heap in the form of the priority queue named 'PQ'.
- Declare two variables 'SUM' = 0, and 'ANS' = 0.
- First push K elements in the queue, Run a loop from i = 0 to i < K, in each iteration:
- Push the 'ENGINEERS_DATA'[i][0] in the 'PQ', which is the ith engineer’s speed in the sorted array.
- Add 'ENGINEERS_DATA'[i][0] to the 'SUM'.
- 'ANS' = max('ANS', 'SUM' * 'ENGINEERS_DATA'[i][0]).
- Now, run a loop from i = K, i < |'ENGINEERS_DATA'|, in each iteration:
- Push the 'ENGINEERS_DATA'[i][0] in the 'PQ'.
- Add 'ENGINEERS_DATA'[i][0] to the 'SUM'.
- Subtract the value from the 'SUM' which is at the top of the 'PQ'.
- Remove the top value from the 'PQ' as well.
- 'ANS' = max('ANS', 'SUM' * 'ENGINEERS_DATA'[i][0]).
- Return the 'ANS' % (10^9 + 7).