{x}
blog image

Maximum Performance of a Team

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 its engineers' speeds multiplied by the minimum efficiency among its engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 109 + 7.

 

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 <= 105
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 105
  • 1 <= efficiency[i] <= 108

Solution Explanation

This problem asks to find the maximum performance of a team formed by selecting at most k engineers from a given set of n engineers. The performance is calculated as the sum of the engineers' speeds multiplied by the minimum efficiency among the selected engineers.

The optimal solution uses a combination of sorting and a priority queue (heap). The core idea is to process engineers in decreasing order of efficiency. For each engineer, we add their speed to the current team's total speed. To ensure we don't exceed k engineers, we maintain a min-heap of the speeds of the engineers currently in the team. If adding a new engineer exceeds k engineers, we remove the engineer with the smallest speed from the heap to maintain the team size.

Algorithm:

  1. Sort: Sort the engineers by efficiency in descending order. This ensures we consider the engineers with higher efficiency first, maximizing the potential performance. We can use a structure like a pair (speed, efficiency) to maintain the association between speed and efficiency for each engineer.

  2. Initialize: Initialize a priority queue (min-heap) to store the speeds of the engineers currently in the team. Also, initialize variables tot (total speed of the current team) and ans (maximum performance found so far) to 0.

  3. Iterate: Iterate through the sorted engineers. For each engineer:

    • Add the engineer's speed to tot.
    • Update ans with the maximum of the current performance (tot * engineer's efficiency) and the current ans.
    • Add the engineer's speed to the min-heap.
    • If the heap size exceeds k, remove the smallest speed from the heap (using heappop) and subtract it from tot.

  4. Return: Return the maximum performance (ans) modulo 10^9 + 7.

Time Complexity Analysis:

  • Sorting the engineers takes O(n log n) time.
  • The iteration through the engineers takes O(n) time.
  • Heap operations (insertion and deletion) take O(log k) time each, and are performed at most O(n) times.

Therefore, the overall time complexity is dominated by sorting, resulting in O(n log n).

Space Complexity Analysis:

The space complexity is determined by the priority queue, which stores at most k elements. Therefore, the space complexity is O(k).

Code Explanations (with minor improvements)

The provided code solutions are already quite efficient, but here are some slight improvements and clarifications:

Python:

import heapq
 
class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        engineers = sorted(zip(efficiency, speed), reverse=True) # Sort by efficiency (descending)
        max_performance = 0
        total_speed = 0
        min_heap = []  # Use heapq for min-heap operations
        mod = 10**9 + 7
 
        for eff, spd in engineers:
            total_speed += spd
            heapq.heappush(min_heap, spd)
            if len(min_heap) > k:
                total_speed -= heapq.heappop(min_heap)
            max_performance = max(max_performance, total_speed * eff)
 
        return max_performance % mod

Java:

import java.util.*;
 
class Solution {
    private static final int MOD = (int) 1e9 + 7;
 
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        int[][] engineers = new int[n][2];
        for (int i = 0; i < n; ++i) {
            engineers[i] = new int[] {efficiency[i], speed[i]};
        }
        Arrays.sort(engineers, (a, b) -> b[0] - a[0]); // Sort by efficiency (descending)
 
        long maxPerformance = 0;
        long totalSpeed = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Use PriorityQueue for min-heap
 
        for (int[] eng : engineers) {
            totalSpeed += eng[1];
            minHeap.offer(eng[1]);
            if (minHeap.size() > k) {
                totalSpeed -= minHeap.poll();
            }
            maxPerformance = Math.max(maxPerformance, totalSpeed * eng[0]);
        }
 
        return (int) (maxPerformance % MOD);
    }
}

C++:

#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        vector<pair<int, int>> engineers(n);
        for (int i = 0; i < n; ++i) {
            engineers[i] = {efficiency[i], speed[i]};
        }
        sort(engineers.rbegin(), engineers.rend()); // Sort by efficiency (descending)
 
        long long maxPerformance = 0;
        long long totalSpeed = 0;
        priority_queue<int, vector<int>, greater<int>> minHeap; // Use priority_queue for min-heap
 
        for (auto& eng : engineers) {
            totalSpeed += eng.second;
            minHeap.push(eng.second);
            if (minHeap.size() > k) {
                totalSpeed -= minHeap.top();
                minHeap.pop();
            }
            maxPerformance = max(maxPerformance, totalSpeed * eng.first);
        }
 
        return (int) (maxPerformance % 1000000007);
    }
};

Go: (This version is improved for clarity and efficiency using container/heap)

package main
 
import (
	"container/heap"
	"sort"
)
 
func maxPerformance(n int, speed []int, efficiency []int, k int) int {
	engineers := make([][]int, n)
	for i := range speed {
		engineers[i] = []int{efficiency[i], speed[i]}
	}
	sort.Slice(engineers, func(i, j int) bool { return engineers[i][0] > engineers[j][0] }) // Sort by efficiency
 
	maxPerf := 0
	totalSpeed := 0
	minHeap := &IntHeap{}
	heap.Init(minHeap)
	mod := 1000000007
 
	for _, eng := range engineers {
		totalSpeed += eng[1]
		heap.Push(minHeap, eng[1])
		if minHeap.Len() > k {
			totalSpeed -= heap.Pop(minHeap).(int)
		}
		maxPerf = max(maxPerf, totalSpeed*eng[0])
	}
 
	return maxPerf % mod
}
 
 
// An IntHeap is a min-heap of ints.
type IntHeap []int
 
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 
func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}
 
func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

These improved versions maintain the same time and space complexity as before but offer better readability and, in some cases, slightly optimized heap management. The use of standard library heap implementations ensures correctness and efficiency.