This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1383 (Hard): Maximum Performance of a Team
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
You are given two integers
nandkand two integer arraysspeedandefficiencyboth of lengthn. There arenengineers numbered from1ton.speed[i]andefficiency[i]represent the speed and efficiency of theith engineer respectively.Choose at most
kdifferent engineers out of thenengineers to form a team with the maximum performance.The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
Return the maximum performance of this team. Since the answer can be a huge number, return it modulo
10^9 + 7.
Examples:
Example 1: Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2 Output: 60 Explanation: We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.
Example 2: Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3 Output: 68 Explanation: This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.
Example 3: Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4 Output: 72
Constraints:
1 <= <= k <= n <= 10^5speed.length == nefficiency.length == n1 <= speed[i] <= 10^51 <= efficiency[i] <= 10^8
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
The trick to this problem, like many best product of x and y problems, is to find a way to iterate through one of the values in order, then evaluate the other value for each combination and take the best result. If we sort the engineers by efficiency, we can iterate downward through the engineers while evaluating the combined speed (totalSpeed) of the ideal group.
Since the index numbers between speed and efficiency correspond to each other, we shouldn't just sort efficiency, however. Instead, we can create another array of arrays (ord) with both stats combined into one array, then sort it based on the efficiency.
As we iterate through the engineers in ord order and add them to the available pool, we know that all the engineers so far are at or higher than minEff, so we're free to only choose the k fastest engineers for our group. To keep track of the sorted order of speeds of the engineers in our available pool, we can use a min priority queue (sppq) or min heap (spheap) structure. This way, we can eliminate the slowest engineer from our pool every time we add an engineer over the k limit. At each stop, we should also find the product of totalSpeed and the current minimum efficiency and update the best result if necessary.
It's important to note that the instructions say "at most" k engineers, so we should start keeping track of best right away. Also, we should remember to modulo 1e9+7 before we return best.
- Time Complexity: O(N * log(N)) where N is the length of speed or efficiency, for the sorting of ord and for the priority queue / heap
- Space Complexity: O(N) for ord and sppq / spheap
Implementation:
The Javascript code would be even faster with a custom heap implementation. The MinPriorityQueue() npm is easier to use, but not as efficient.
Javascript is faster by passing only the index reference into the priority queue, rather than combining both stats into an array before storage.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var maxPerformance = function(n, speed, efficiency, k) {
let ord = Array.from({length: n}, (_,i) => i)
ord.sort((a,b) => efficiency[b] - efficiency[a])
let sppq = new MinPriorityQueue(),
totalSpeed = 0n, best = 0n
for (let eng of ord) {
sppq.enqueue(speed[eng])
if (sppq.size() <= k) totalSpeed += BigInt(speed[eng])
else totalSpeed += BigInt(speed[eng] - sppq.dequeue().element)
let res = totalSpeed * BigInt(efficiency[eng])
if (res > best) best = res
}
return best % 1000000007n
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
ord = sorted(zip(efficiency, speed), reverse=True)
spheap, totalSpeed, best = [], 0, 0
for eff, spd in ord:
heappush(spheap, spd)
if len(spheap) <= k: totalSpeed += spd
else: totalSpeed += spd - heappop(spheap)
best = max(best, totalSpeed * eff)
return best % 1000000007
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
int[][] ord = new int[n][2];
for (int i = 0; i < n; i++)
ord[i] = new int[] {efficiency[i], speed[i]};
Arrays.sort(ord, (a, b) -> Integer.compare(b[0], a[0]));
PriorityQueue<Integer> sppq = new PriorityQueue<>();
long totalSpeed = 0, best = 0;
for (int[] pair : ord) {
int spd = pair[1];
sppq.add(spd);
if (sppq.size() <= k) totalSpeed += spd;
else totalSpeed += spd - sppq.poll();
best = Math.max(best, totalSpeed * pair[0]);
}
return (int)(best % 1000000007);
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
vector<pair<int, int>> ord;
for (int i = 0; i < n; i++)
ord.push_back({efficiency[i], speed[i]});
sort(ord.rbegin(), ord.rend());
priority_queue<int> sppq;
long totalSpeed = 0, best = 0;
for (auto& p : ord) {
int spd = p.second;
sppq.push(-spd);
if (sppq.size() <= k) totalSpeed += spd;
else {
totalSpeed += spd + sppq.top();
sppq.pop();
}
best = max(best, totalSpeed * p.first);
}
return best % 1000000007;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-06-05T10:01:26+00:00) Solution: Maximum Performance of a Team. Retrieved from https://www.scien.cx/2021/06/05/solution-maximum-performance-of-a-team/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.