Code Implementation

import heapq

class Solution:
    def maxPerformance(self, n, speed, efficiency, k):
        MOD = 10**9 + 7
        engineers = sorted(zip(efficiency, speed), reverse=True)
        speed_heap = []
        speed_sum = 0
        max_perf = 0

        for curr_eff, curr_speed in engineers:
            heapq.heappush(speed_heap, curr_speed)
            speed_sum += curr_speed

            if len(speed_heap) > k:
                speed_sum -= heapq.heappop(speed_heap)

            max_perf = max(max_perf, speed_sum * curr_eff)

        return max_perf % MOD
      

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        const int MOD = 1e9 + 7;
        vector<pair<int,int>> engineers;
        for (int i = 0; i < n; ++i)
            engineers.push_back({efficiency[i], speed[i]});
        sort(engineers.rbegin(), engineers.rend());

        priority_queue<int, vector<int>, greater<int>> minHeap;
        long speedSum = 0, maxPerf = 0;
        for (auto& [eff, spd] : engineers) {
            minHeap.push(spd);
            speedSum += spd;
            if (minHeap.size() > k) {
                speedSum -= minHeap.top();
                minHeap.pop();
            }
            maxPerf = max(maxPerf, speedSum * eff);
        }
        return maxPerf % MOD;
    }
};
      

import java.util.*;

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        int MOD = 1_000_000_007;
        int[][] engineers = new int[n][2];
        for (int i = 0; i < n; ++i) {
            engineers[i][0] = efficiency[i];
            engineers[i][1] = speed[i];
        }
        Arrays.sort(engineers, (a, b) -> b[0] - a[0]);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        long speedSum = 0, maxPerf = 0;
        for (int[] eng : engineers) {
            minHeap.add(eng[1]);
            speedSum += eng[1];
            if (minHeap.size() > k) {
                speedSum -= minHeap.poll();
            }
            maxPerf = Math.max(maxPerf, speedSum * eng[0]);
        }
        return (int)(maxPerf % MOD);
    }
}
      

/**
 * @param {number} n
 * @param {number[]} speed
 * @param {number[]} efficiency
 * @param {number} k
 * @return {number}
 */
var maxPerformance = function(n, speed, efficiency, k) {
    const MOD = 1e9 + 7;
    let engineers = [];
    for (let i = 0; i < n; ++i)
        engineers.push([efficiency[i], speed[i]]);
    engineers.sort((a, b) => b[0] - a[0]);

    let minHeap = [];
    let speedSum = 0, maxPerf = 0;

    function pushHeap(val) {
        minHeap.push(val);
        minHeap.sort((a, b) => a - b);
    }
    function popHeap() {
        return minHeap.shift();
    }

    for (let [eff, spd] of engineers) {
        pushHeap(spd);
        speedSum += spd;
        if (minHeap.length > k) {
            speedSum -= popHeap();
        }
        maxPerf = Math.max(maxPerf, speedSum * eff);
    }
    return maxPerf % MOD;
};
      

Problem Description

You are given n engineers, where each engineer has a speed and an efficiency. You are also given an integer k, representing the maximum number of engineers you can select to form a team.

The performance of a team is defined as the sum of the selected engineers' speeds multiplied by the minimum efficiency among the selected engineers.

Your task is to select at most k engineers out of n to form a team with the maximum possible performance.

• Each engineer can be selected at most once (no reuse).
• Return the maximum performance value modulo 10^9 + 7.

Constraints:

• 1 <= n <= 10^5
• 1 <= speed[i], efficiency[i] <= 10^5
• 1 <= k <= n

Thought Process

At first glance, the problem seems to require checking all possible combinations of up to k engineers and calculating their performance. However, with up to 10^5 engineers, this brute-force approach is infeasible.

We need to maximize the sum of selected speeds while keeping the minimum efficiency as high as possible. Since the performance is sum of speeds × minimum efficiency, the minimum efficiency acts as a bottleneck. If we add an engineer with lower efficiency, the team's minimum efficiency drops, but the speed sum may increase.

The key is to find a way to balance these two factors efficiently. We should consider engineers in order of efficiency, focusing on maximizing the sum of the top k speeds for each possible minimum efficiency.

Solution Approach

• Step 1: Pair up each engineer's efficiency and speed into a tuple or object.
• Step 2: Sort all engineers in descending order of efficiency. This ensures that as we iterate, the current engineer's efficiency is the minimum for any team that includes them and all previous engineers.
• Step 3: Use a min-heap (priority queue) to keep track of the k largest speeds among the engineers considered so far. The heap size never exceeds k.
• Step 4: For each engineer in the sorted list:
  • Add their speed to the heap and to a running speed sum.
  • If the heap exceeds k elements, remove the smallest speed (so only the top k speeds are considered).
  • Calculate the performance as speed sum × current efficiency (since current efficiency is the minimum in this selection).
  • Update the maximum performance found so far.
• Step 5: After processing all engineers, return the maximum performance modulo 10^9 + 7.

This approach ensures we always have the best possible sum of speeds for any given minimum efficiency, while never exceeding k engineers.

Example Walkthrough

Let's use the following example:
n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2

1. Pair and sort engineers by efficiency descending:
   [(9,1), (7,5), (5,2), (4,10), (3,3), (2,8)]
2. Initialize an empty heap and speed sum = 0, max performance = 0.
3. Iterate through sorted engineers:
   • First: (9,1). Heap: [1], speed sum: 1. Performance: 1×9=9.
   • Second: (7,5). Heap: [1,5], speed sum: 6. Performance: 6×7=42.
   • Third: (5,2). Heap: [1,5,2] (size>2, pop 1). Heap: [2,5], speed sum: 7. Performance: 7×5=35.
   • Fourth: (4,10). Heap: [2,5,10] (size>2, pop 2). Heap: [5,10], speed sum: 15. Performance: 15×4=60.
   • Fifth: (3,3). Heap: [3,5,10] (size>2, pop 3). Heap: [5,10], speed sum: 15. Performance: 15×3=45.
   • Sixth: (2,8). Heap: [5,8,10] (size>2, pop 5). Heap: [8,10], speed sum: 18. Performance: 18×2=36.
4. The maximum performance found is 60.

Time and Space Complexity

• Brute-force approach: Would require checking all possible subsets of up to k engineers, which is exponential in time and not feasible for large n.
• Optimized approach:
  • Sorting engineers: O(n \log n)
  • For each engineer, heap operations take O(\log k) time, for n engineers: O(n \log k)
  • Total time complexity: O(n \log n + n \log k)
  • Space complexity: O(n) for storing engineers and up to O(k) for the heap.

Summary

To maximize the team's performance, we sort engineers by efficiency and use a min-heap to keep track of the top k speeds. This allows us to efficiently consider every possible minimum efficiency and the best speeds to pair with it. By always updating the performance after adding each engineer and maintaining only the k largest speeds, we ensure the solution is both optimal and efficient.

The elegant part of this approach is how it leverages sorting and a heap to reduce the problem's complexity from exponential to nearly linear, making it practical for large datasets.