1383. Maximum Performance of a Team


Problem Description

In this problem, we are given two integer values n (the number of engineers) and k (the maximum number of engineers we can select), along with two integer arrays speed and efficiency, each of length n. The speed array represents the speed of each engineer, while the efficiency array represents the efficiency of each engineer.

Our task is to form a team with at most k engineers to achieve the maximum performance. The performance of a team is defined as the sum of the speeds of the selected engineers multiplied by the minimum efficiency among them.

We need to calculate the maximum possible performance of a team formed under these constraints and return this maximum value modulo 10^9 + 7 to handle very large numbers.

Intuition

To achieve the maximum performance, we need to consider both speed and efficiency in our selection strategy. A greedy approach can help us select the most suitable candidates.

One key insight is that if we pick an engineer with a certain efficiency, then the total efficiency of the team cannot exceed this value. Therefore, to maximize the team's performance at each step, we aim to add engineers with the highest speeds possible without dropping the minimum efficiency of the team below the current candidate's efficiency.

Here's how we arrive at the solution approach:

  1. We pair the speed and efficiency for each engineer and then sort these pairs in descending order of efficiency. This ensures that as we iterate through the engineers, we maintain the invariant that we only consider teams where the minimum efficiency is at least as much as the current engineer's efficiency.

  2. We use a min-heap (which in Python is conveniently implemented through the heapq module) to keep track of the smallest speeds in our current team selection. This is useful because, if the team has more than k engineers, we will need to remove the one with the smallest speed to add a new one.

  3. As we iterate through the sorted engineer list, we do the following:

    • Add the current engineer's speed to the total speed (tot).
    • Calculate the current performance by multiplying the total speed with the engineer's efficiency.
    • Check if this current performance is greater than the maximum performance found so far and update ans if it is.
    • Add the current engineer's speed to the heap.
    • If the heap's size exceeds k, remove the smallest speed from it and adjust the total speed (tot) accordingly.
  4. The largest value found during this process is our maximum performance. Because large numbers are involved, we return the result modulo 10^9 + 7.

This approach ensures that at any point, the team is formed by choosing engineers that contribute maximally to the speed while being limited by the engineer with the lowest efficiency in the team.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution makes good use of both sorting and a min-heap to achieve the desired outcome. Here's a step-by-step explanation of the implementation:

  1. Sorting by Efficiency: We start by creating a list of tuples t that pairs each engineer's speed with their corresponding efficiency. We then sort this list in descending order based on efficiency. This allows us to process the engineers in order of decreasing efficiency, so at each step, we consider the highest possible efficiency for the team and try to maximize speed.

    1t = sorted(zip(speed, efficiency), key=lambda x: -x[1])
  2. Initial Declarations: We initialize three variables:

    • ans to track the maximum performance encountered so far.
    • tot to keep the running sum of the speeds of the engineers in the current team.
    • mod to store the modulus value of 10^9 + 7 for use at the end of the calculation.
    1ans = tot = 0
    2mod = 10**9 + 7
  3. Min-Heap Usage: We declare a list h which will serve as our min-heap using the heapq library. This is where we will store the speeds of the engineers we choose for our team. A min-heap allows us to efficiently retrieve and remove the engineer with the smallest speed when needed.

    1h = []
  4. Iterating over Engineers: We now iterate over each engineer in the sorted list t. For each engineer, we perform the following steps:

    • Add the engineer's speed to tot.
    • Calculate a potential maximum performance tot * e and compare this with ans, updating ans if it's larger. This step considers that the current engineer's efficiency sets the new minimum efficiency for the team.
    • Add the engineer's speed to the min-heap.
    • If the heap size reaches k, we remove the smallest speed using heappop, which would be the one at the root of the min-heap, and subtract that value from tot. This step ensures that the team size does not exceed k.
    1for s, e in t:
    2    tot += s
    3    ans = max(ans, tot * e)
    4    heappush(h, s)
    5    if len(h) == k:
    6        tot -= heappop(h)
  5. Modulo Operation: After the loop is done, ans holds the maximum performance value. We return ans % mod to ensure the result adheres to the modulo constraint.

    1return ans % mod

The use of sorting ensures that we're always considering engineers in the order of their efficiency, from highest to lowest, which is crucial for maximizing performance. The min-heap is essential for managing the team size and quickly ejecting the least-contributing member (in terms of speed) when the team exceeds the size k. With this strategy, the complexity of the solution is dictated by the sorting step, which is O(n log n), and the heap operations, which have O(log k) complexity for each of the n engineers, making the overall complexity O(n log n + n log k).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Let's illustrate the solution approach with a small example:

  • Suppose we have n = 4 engineers and k = 2 as the maximum number of engineers we can select.
  • Let's assume the speed array is [5, 2, 3, 9] and the efficiency array is [10, 1, 4, 7].

Following the steps described in the solution approach:

  1. Sorting by Efficiency: We first pair each engineer's speed with their corresponding efficiency and sort the data by efficiency in descending order.

    Pairs formed: [(5, 10), (2, 1), (3, 4), (9, 7)]

    After sorting by efficiency: [(5, 10), (9, 7), (3, 4), (2, 1)]

  2. Initial Declarations:

    Variable initialization:

    • ans = 0
    • tot = 0
    • mod = 10^9 + 7
  3. Min-Heap Usage:

    Initialize an empty min-heap h.

  4. Iterating over Engineers: Now we consider each engineer in t.

    • For engineer (5, 10):
      • tot becomes 5.
      • Potential performance: 5 * 10 = 50. ans is updated to 50.
      • Add speed 5 to the heap. Heap h: [5].
    • For engineer (9, 7):
      • tot becomes 14 (5 + 9).
      • Potential performance: 14 * 7 = 98. ans is updated to 98.
      • Add speed 9 to the heap. Heap h: [5, 9].
    • For engineer (3, 4):
      • tot becomes 17 (14 + 3).
      • Potential performance: 17 * 4 = 68, which is less than ans (98), so no update is needed.
      • Add speed 3 to the heap. Heap h: [3, 9, 5].
      • Since the heap now exceeds k (size is 3), we remove the smallest speed 3 (heap pop). tot becomes 14 (17 - 3).
    • For engineer (2, 1):
      • tot becomes 16 (14 + 2).
      • Potential performance: 16 * 1 = 16, which is less than ans (98), so no update is needed.
      • Add speed 2 to the heap. Heap h: [2, 9, 5].
      • Again, since the heap size exceeds k, we remove the smallest speed 2 (heap pop). tot becomes 14 (16 - 2).

    The loop ends and the largest value found during this process is ans = 98.

  5. Modulo Operation:

    Finally, we return ans % mod, which is 98 % (10^9 + 7) = 98 because 98 is already less than 10^9 + 7.

By the end of this process, we've determined that the maximum performance that can be achieved with a team of at most k engineers is 98.

Solution Implementation

1from typing import List
2from heapq import heappush, heappop
3
4class Solution:
5    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
6        # Combine the speed and efficiency into a single list of tuples
7        # and sort it in descending order of efficiency.
8        combined = sorted(zip(speed, efficiency), key=lambda x: -x[1])
9      
10        max_performance = total_speed = 0
11        mod = 10**9 + 7
12        min_speed_heap = []  # A min-heap to track the smallest speeds.
13      
14        # Iterate through the engineers sorted by efficiency.
15        for curr_speed, curr_efficiency in combined:
16            # Add the current engineer's speed to the total speed.
17            total_speed += curr_speed
18          
19            # Calculate the current performance with the current engineer.
20            max_performance = max(max_performance, total_speed * curr_efficiency)
21          
22            # Add the current speed to the min heap.
23            heappush(min_speed_heap, curr_speed)
24          
25            # If the size of the team exceeds k, remove the engineer with the smallest speed.
26            if len(min_speed_heap) > k:
27                # Remove the smallest speed from the total speed as we pop from the heap.
28                total_speed -= heappop(min_speed_heap)
29      
30        # The result could be large; we return the result modulo 10^9 + 7.
31        return max_performance % mod
32
1class Solution {
2    private static final int MODULUS = (int) 1e9 + 7; // Define a constant for the modulus value
3
4    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
5        // Create an array to store speed and efficiency pairs
6        int[][] engineers = new int[n][2]; 
7        for (int i = 0; i < n; ++i) {
8            engineers[i] = new int[] {speed[i], efficiency[i]};
9        }
10      
11        // Sort the engineers array by efficiency in descending order
12        Arrays.sort(engineers, (a, b) -> b[1] - a[1]);
13      
14        // Use a min heap to keep track of the k highest speeds
15        PriorityQueue<Integer> speedQueue = new PriorityQueue<>();
16      
17        long totalSpeed = 0;      // Total speed of the selected engineers
18        long maxPerformance = 0;  // Max performance found so far
19      
20        // Iterate through the sorted engineers
21        for (var engineer : engineers) {
22            int currentSpeed = engineer[0];
23            int currentEfficiency = engineer[1];
24          
25            // Add the current speed to the total and update the max performance
26            totalSpeed += currentSpeed;
27            maxPerformance = Math.max(maxPerformance, totalSpeed * currentEfficiency);
28          
29            // Add the current speed to the speed queue
30            speedQueue.offer(currentSpeed);
31          
32            // If the size of the speedQueue exceeds k, remove the slowest engineer
33            if (speedQueue.size() > k) {
34                // Polling removes the smallest element (min heap property)
35                totalSpeed -= speedQueue.poll();
36            }
37        }
38      
39        // Return the max performance modulo the defined modulus to prevent overflow
40        return (int) (maxPerformance % MODULUS);
41    }
42}
43
1#include <vector>
2#include <queue>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9    int maxPerformance(int numEngineers, vector<int>& speeds, vector<int>& efficiencies, int maxTeamSize) {
10        // Pair speed with efficiency, and sort engineers by increasing efficiency
11        vector<pair<int, int>> engineerPair(numEngineers);
12        for (int i = 0; i < numEngineers; ++i) {
13            engineerPair[i] = {efficiencies[i], speeds[i]};
14        }
15        // Sort the engineers primarily by efficiency in descending order
16        sort(engineerPair.rbegin(), engineerPair.rend());
17
18        // Min heap to keep track of the lowest speed in the current team for easy removal
19        priority_queue<int, vector<int>, greater<int>> speedHeap;
20        long long maxPerformance = 0, totalSpeed = 0;
21        int modulus = 1e9 + 7; // For taking modulo after calculations to prevent overflow
22
23        for (auto& engineer : engineerPair) {
24            int currentSpeed = engineer.second;
25            int currentEfficiency = engineer.first;
26
27            // Add the current engineer's speed to the total speed
28            totalSpeed += currentSpeed;
29
30            // Update max performance with the new team configuration
31            // Here, the performance is calculated as the product of total speed and
32            // the efficiency of the least efficient engineer in the team
33            maxPerformance = max(maxPerformance, totalSpeed * currentEfficiency);
34
35            // Add the current speed to the min heap
36            speedHeap.push(currentSpeed);
37
38            // If the team size exceeds the max allowed size, remove the engineer 
39            // with the lowest speed from the team
40            if (speedHeap.size() > maxTeamSize) {
41                totalSpeed -= speedHeap.top(); // Subtract the lowest speed
42                speedHeap.pop(); // Remove the lowest speed
43            }
44        }
45
46        // Return the maximum performance modulo 1e9+7
47        return static_cast<int>(maxPerformance % modulus);
48    }
49};
50
1type Engineer = {
2    speed: number;
3    efficiency: number;
4};
5
6function maxPerformance(numEngineers: number, speeds: number[], efficiencies: number[], maxTeamSize: number): number {
7    // Create an array of objects containing speed and efficiency
8    const engineers: Engineer[] = speeds.map((speed, index) => ({
9        speed: speed,
10        efficiency: efficiencies[index],
11    }));
12
13    // Sort engineers primarily by efficiency in descending order
14    engineers.sort((a, b) => b.efficiency - a.efficiency);
15
16    // Min heap to keep track of the lowest speed in the current team for easy removal
17    const speedHeap: number[] = [];
18    let maxPerformance: number = 0;
19    let totalSpeed: number = 0;
20    const modulus: number = 1e9 + 7; // For taking modulo after calculations to prevent overflow
21
22    engineers.forEach(engineer => {
23        totalSpeed += engineer.speed;
24        // Calculate the maximum performance with the new team configuration
25        maxPerformance = Math.max(maxPerformance, totalSpeed * engineer.efficiency);
26
27        // Add current speed to the heap
28        speedHeap.push(engineer.speed);
29        speedHeap.sort((a, b) => a - b); // Convert array to a min heap by sorting in ascending order
30
31        // If the team size exceeds the max allowed size, remove the engineer with the lowest speed
32        if (speedHeap.length > maxTeamSize) {
33            totalSpeed -= speedHeap.shift() as number; // Shift operation removes the first element, which is the smallest due to min-heap property
34        }
35    });
36
37    return maxPerformance % modulus;
38}
39

Time and Space Complexity

Time Complexity

The given Python code sorts an array of tuples based on the efficiency, uses a min-heap for maintaining the k highest speeds, and iterates through the sorted list to calculate the answer.

  1. Sorting the array of tuples based on efficiency has a time complexity of O(n log n) where n is the number of engineers.
  2. Iterating through the sorted array to calculate the maximum performance occurs in O(n), as each element is visited exactly once.
  3. For every engineer processed inside the loop, it may add an element to the min-heap, which is O(log k) where k is the maximum team size. However, this operation will only happen up to k times because once the heap size reaches k, engineers are popped out for every new engineer added.
  4. The 'heappop' operation, which occurs when the heap reaches the size k, is also O(log k).

Therefore, the total time complexity combines the sorting and the heap operations: O(n log n) + O(n log k). Since k can be at most n, in the worst case, it simplifies to O(n log n).

Space Complexity

The space complexity should account for the sorted array of tuples, and the min-heap used to store up to k elements:

  1. The sorted array of tuples has a space complexity of O(n), as it stores n pairs of (speed, efficiency).
  2. The min-heap also has a space complexity of O(k) as it may store up to k elements at a time.

The total space complexity is the higher of the two: O(n) when n is greater than k, otherwise O(k). In asymptotic notation, we express this as O(max(n, k)), but since k <= n, it simplifies to O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄