DEV Community

loading...
Cover image for Solution: Maximum Performance of a Team

Solution: Maximum Performance of a Team

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・4 min read

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 n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers 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^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= 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
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (2)

Collapse
taviscatjajodia profile image
Tushar Jajodia

Such an Amazing Explanation.

Collapse
seanpgallivan profile image
seanpgallivan Author

Thanks!