Skip to content

1383. Maximum Performance of a Team 👍

  • Time: $O(\texttt{sort} + n\log k)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  // Similar to 857. Minimum Cost to Hire K Workers
  public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
    final int MOD = 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 % MOD);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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:
    MOD = 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 % MOD