Maximum Performance of a Team

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in company
Uber

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5 2
3 2 4 3 1
5 2 4 3 2
Sample Output 1:
28
Explanation for sample input 1:
We get the maximum performance of the team by selecting the following engineers:
1. 1st engineer, speed = 3, efficiency = 5.
2. 3rd engineer, speed = 4, efficiency = 4.
So, the performance of the team = (3 + 4) * min(5,4) = 28. There is no other way to get a performance greater than 28.
Sample Input 2:
1
5 2
3 2 4 1 2
5 1 2 3 2
Sample Output 2:
15
Explanation for sample input 2:
We get the team’s maximum performance by selecting only one engineer, i.e., the first engineer, speed = 3, and efficiency = 5. So, the performance become = 3 * 5 = 15. 

Notice that we can also form a team with the two engineers, but it is not possible to get the performance greater than 15 in any other way.
Hint

Think of sorting based on efficiency.

Approaches (1)
Sorting and Min-Heap
  • 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).
Time Complexity

O(N * logN), where ‘N’ is the number of engineers.

 

We are storing the engineers based on their ‘EFFICIENCY’, which will take ‘O(N*logN)’. To perform the ‘min-heap’ operations, it will take O(logK) because the heap’s maximum size can go up to ‘K’, and we are performing these operations ‘N’ times. So, to deal with the heap we require ‘O(N*logK)’ time. Hence, the overall time complexity will be O(N*logN + N*logK) which is nothing but the O(N * logN).

Space Complexity

O(N), where ‘N’ is the number of engineers.

 

As we are using an array to store the engineer’s data, that is of the size ‘N’. Hence, the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Maximum Performance of a Team
Full screen
Console