Maximum Performance of a Team

Problem

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 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

Solution

Method 1 – Greedy + Heap

Intuition

To maximize performance, we want the largest possible sum of speeds, but the team's minimum efficiency acts as a bottleneck. By sorting engineers by efficiency (from high to low), we can always ensure the current engineer's efficiency is the minimum in the current team. We use a min-heap to keep track of the top k speeds.

Approach

1. Pair each engineer's efficiency and speed.
2. Sort engineers in descending order of efficiency.
3. Initialize a min-heap to store the speeds of selected engineers and a variable to track the sum of speeds.
4. Iterate through the sorted engineers:

• Add the current engineer's speed to the heap and update the sum.
• If the heap size exceeds k, remove the smallest speed and update the sum.
• Calculate performance as sum_of_speeds * current_efficiency and update the answer if it's higher.

5. Return the answer modulo 10^9 + 7.

Code

C++

class Solution {
public:
   int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
      const int MOD = 1e9 + 7;
      vector<pair<int, int>> eng;
      for (int i = 0; i < n; ++i)
        eng.push_back({efficiency[i], speed[i]});
      sort(eng.rbegin(), eng.rend());
      priority_queue<int, vector<int>, greater<int>> heap;
      long sSum = 0, ans = 0;
      for (auto& [e, s] : eng) {
        heap.push(s);
        sSum += s;
        if (heap.size() > k) {
           sSum -= heap.top();
           heap.pop();
        }
        ans = max(ans, sSum * e);
      }
      return ans % MOD;
   }
};

Go

func maxPerformance(n int, speed []int, efficiency []int, k int) int {
   MOD := int(1e9 + 7)
   type pair struct{ e, s int }
   eng := make([]pair, n)
   for i := 0; i < n; i++ {
      eng[i] = pair{efficiency[i], speed[i]}
   }
   sort.Slice(eng, func(i, j int) bool { return eng[i].e > eng[j].e })
   heap := &IntHeap{}
   heap.Init()
   sSum, ans := 0, 0
   for _, es := range eng {
      heap.Push(es.s)
      sSum += es.s
      if heap.Len() > k {
        sSum -= heap.Pop().(int)
      }
      if val := sSum * es.e; val > ans {
        ans = val
      }
   }
   return ans % MOD
}

// IntHeap implements heap.Interface for ints (min-heap)
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 interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
   old := *h
   n := len(old)
   x := old[n-1]
   *h = old[:n-1]
   return x
}

Java

class Solution {
   public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
      int MOD = (int)1e9 + 7;
      int[][] eng = new int[n][2];
      for (int i = 0; i < n; i++) {
        eng[i][0] = efficiency[i];
        eng[i][1] = speed[i];
      }
      Arrays.sort(eng, (a, b) -> b[0] - a[0]);
      PriorityQueue<Integer> heap = new PriorityQueue<>();
      long sSum = 0, ans = 0;
      for (int[] e : eng) {
        heap.offer(e[1]);
        sSum += e[1];
        if (heap.size() > k) sSum -= heap.poll();
        ans = Math.max(ans, sSum * e[0]);
      }
      return (int)(ans % MOD);
   }
}

Kotlin

class Solution {
   fun maxPerformance(n: Int, speed: IntArray, efficiency: IntArray, k: Int): Int {
      val MOD = 1_000_000_007
      val eng = efficiency.zip(speed).sortedByDescending { it.first }
      val heap = java.util.PriorityQueue<Int>()
      var sSum = 0L
      var ans = 0L
      for ((e, s) in eng) {
        heap.add(s)
        sSum += s
        if (heap.size > k) sSum -= heap.poll()
        ans = maxOf(ans, sSum * e)
      }
      return (ans % MOD).toInt()
   }
}

Python

class Solution:
   def maxPerformance(self, n: int, speed: list[int], efficiency: list[int], k: int) -> int:
      MOD = 10**9 + 7
      eng = sorted(zip(efficiency, speed), reverse=True)
      heap = []
      s_sum = 0
      ans = 0
      import heapq
      for e, s in eng:
        heapq.heappush(heap, s)
        s_sum += s
        if len(heap) > k:
           s_sum -= heapq.heappop(heap)
        ans = max(ans, s_sum * e)
      return ans % MOD

Rust

impl Solution {
   pub fn max_performance(n: i32, speed: Vec<i32>, efficiency: Vec<i32>, k: i32) -> i32 {
      use std::collections::BinaryHeap;
      let mut eng: Vec<(i32, i32)> = efficiency.into_iter().zip(speed.into_iter()).collect();
      eng.sort_unstable_by(|a, b| b.0.cmp(&a.0));
      let mut heap = BinaryHeap::new();
      let mut s_sum: i64 = 0;
      let mut ans: i64 = 0;
      for (e, s) in eng {
        heap.push(std::cmp::Reverse(s));
        s_sum += s as i64;
        if heap.len() > k as usize {
           if let Some(std::cmp::Reverse(x)) = heap.pop() {
              s_sum -= x as i64;
           }
        }
        ans = ans.max(s_sum * e as i64);
      }
      (ans % 1_000_000_007) as i32
   }
}

Complexity

• Time: O(n log n) (sorting + heap operations)
• Space: O(n) (for heap and auxiliary arrays)