1383. Maximum Performance of a Team LeetCode Solution

In this guide, you will get 1383. Maximum Performance of a Team LeetCode Solution with the best time and space complexity. The solution to Maximum Performance of a Team problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Performance of a Team solution in C++
Maximum Performance of a Team solution in Java
Maximum Performance of a Team solution in Python
Additional Resources

1383. Maximum Performance of a Team LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(\texttt{sort} + n\log k)
Space Complexity: O(n)

1383. Maximum Performance of a Team LeetCode Solution in C++

class Solution {
 public:
  // Similar to 857. Minimum Cost to Hire K Workers
  int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency,
                     int k) {
    constexpr int kMod = 1'000'000'007;
    long ans = 0;
    long speedSum = 0;
    // (efficiency[i], speed[i]) sorted by efficiency[i] in descending order
    vector<pair<int, int>> A;
    priority_queue<int, vector<int>, greater<>> minHeap;

    for (int i = 0; i < n; ++i)
      A.emplace_back(efficiency[i], speed[i]);

    ranges::sort(A, greater<>());

    for (const auto& [e, s] : A) {
      minHeap.push(s);
      speedSum += s;
      if (minHeap.size() > k)
        speedSum -= minHeap.top(), minHeap.pop();
      ans = max(ans, speedSum * e);
    }

    return ans % kMod;
  }
};
/* code provided by PROGIEZ */

1383. Maximum Performance of a Team LeetCode Solution in Java

class Solution {
  // Similar to 857. Minimum Cost to Hire K Workers
  public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
    final int kMod = 1_000_000_007;
    long ans = 0;
    long speedSum = 0;
    // (efficiency[i], speed[i]) sorted by efficiency[i] in descending order
    Pair<Integer, Integer>[] A = new Pair[n];
    Queue<Integer> minHeap = new PriorityQueue<>();

    for (int i = 0; i < n; ++i)
      A[i] = new Pair<>(efficiency[i], speed[i]);

    Arrays.sort(A, Comparator.comparing(Pair::getKey, Comparator.reverseOrder()));

    for (Pair<Integer, Integer> a : A) {
      final int e = a.getKey();
      final int s = a.getValue();
      minHeap.offer(s);
      speedSum += s;
      if (minHeap.size() > k)
        speedSum -= minHeap.poll();
      ans = Math.max(ans, speedSum * e);
    }

    return (int) (ans % kMod);
  }
}
// code provided by PROGIEZ

1383. Maximum Performance of a Team LeetCode Solution in Python

class Solution:
  # Similar to 857. Minimum Cost to Hire K Workers
  def maxPerformance(
      self,
      n: int,
      speed: list[int],
      efficiency: list[int],
      k: int,
  ) -> int:
    kMod = 1_000_000_007
    ans = 0
    speedSum = 0
    # (efficiency[i], speed[i]) sorted by efficiency[i] in descending order
    A = sorted([(e, s) for s, e in zip(speed, efficiency)], reverse=True)
    minHeap = []

    for e, s in A:
      heapq.heappush(minHeap, s)
      speedSum += s
      if len(minHeap) > k:
        speedSum -= heapq.heappop(minHeap)
      ans = max(ans, speedSum * e)

    return ans % kMod
 # code by PROGIEZ