Problem Definition

The objective is to select a team of at most k engineers from a pool of n candidates to maximize the team's performance metric. This metric is defined as the sum of the selected engineers' speeds multiplied by the minimum efficiency value among them. Given arrays representing the speed and efficiency of each engineer, the task is to compute the maximum possible performance value, returned modulo $10^9 + 7$.

Greedy Strategy with Priority Queue

A brute-force approach is infeasible due to the constraints. The optimal solution utilizes a greedy algorithm combined with a min-heap (priority queue).

The key insight is that for any team, the efficiency is determined by the member with the lowest efficiency. If we iterate through engineers sorted by efficiency in descending order, the current engineer's efficiency acts as a lower bound (the minimum efficiency) for any team formed up to that point. To maximize performance for this efficiency constraint, we must maximize the sum of speeds.

The algorithm maintains a running sum of speeds. As we iterate, we add the current engineer's speed to the sum. If the team size exceeds k, we remove the engineer with the lowest speed from the team. A min-heap is the ideal data structure for this, allowing efficient retrieval and removal of the smallest speed value.

Algorithm Steps

1. Create an array of objects pairing each engineer's speed and efficiency.
2. Sort this array by efficiency in descending order.
3. Initialize a min-heap to store speeds and a variable to track the sum of speeds in the current team.
4. Iterate through the sorted engineers:
   • Add the current speed to the heap and the running sum.
   • If the heap size exceeds k, extract the minimum speed from the heap and subtract it from the sum.
   • Calculate the current performance: sum_of_speeds * current_efficiency.
   • Update the maximum performance found so far.
5. Return the maximum performance modulo $10^9 + 7$.

Implementation Details

To handle potentially large numbers that exceed the safe integer limit of standard JavaScript numbers, the implementation below uses BigInt for performance calculations. A custom MinHeap class is implemented to manage the speed values.

class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    bubbleUp(index) {
        while (index > 0) {
            let parent = Math.floor((index - 1) / 2);
            if (this.heap[parent] <= this.heap[index]) break;
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
            index = parent;
        }
    }

    pop() {
        if (this.heap.length === 0) return null;
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown(0);
        }
        return min;
    }

    sinkDown(index) {
        const length = this.heap.length;
        while (true) {
            let left = 2 * index + 1;
            let right = 2 * index + 2;
            let swapIdx = index;

            if (left < length && this.heap[left] < this.heap[swapIdx]) {
                swapIdx = left;
            }
            if (right < length && this.heap[right] < this.heap[swapIdx]) {
                swapIdx = right;
            }
            if (swapIdx === index) break;
            [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
            index = swapIdx;
        }
    }

    size() {
        return this.heap.length;
    }
}

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

    const minHeap = new MinHeap();
    let speedSum = 0;
    let maxPerf = 0n;

    for (const eng of engineers) {
        // Current efficiency is the minimum efficiency for the team so far
        speedSum += eng.s;
        minHeap.push(eng.s);

        // Keep only top k speeds
        if (minHeap.size() > k) {
            const removed = minHeap.pop();
            speedSum -= removed;
        }

        // Calculate performance with BigInt
        const currentPerf = BigInt(speedSum) * BigInt(eng.e);
        if (currentPerf > maxPerf) {
            maxPerf = currentPerf;
        }
    }

    return Number(maxPerf % MOD);
};