← Back to Index

📚 Maximum Performance of a Team – Java Cheat Sheet

📌 What Is It?

The Maximum Performance of a Team problem involves selecting up to K engineers from a pool of engineers, each with a given speed and efficiency, to maximize the team's performance. The performance is calculated as the sum of the selected engineers' speeds multiplied by the minimum efficiency among them.

This problem can be solved using a max-heap to track the engineers with the highest speeds.

🧱 Pattern Template

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        int MOD = 1_000_000_007;

        Engineer[] engineers = new Engineer[n];
        for (int i = 0; i < n; i++) {
            engineers[i] = new Engineer(speed[i], efficiency[i]);
        }

        Arrays.sort(engineers, (a, b) -> b.efficiency - a.efficiency);

        PriorityQueue<Integer> speedHeap = new PriorityQueue<>();
        long speedSum = 0, maxPerformance = 0;

        for (Engineer engineer : engineers) {
            speedHeap.offer(engineer.speed);
            speedSum += engineer.speed;

            if (speedHeap.size() > k) {
                speedSum -= speedHeap.poll();
            }

            maxPerformance = Math.max(maxPerformance, speedSum * engineer.efficiency);
        }

        return (int) (maxPerformance % MOD);
    }

    class Engineer {
        int speed;
        int efficiency;

        Engineer(int speed, int efficiency) {
            this.speed = speed;
            this.efficiency = efficiency;
        }
    }
}

📊 Time Complexity

• Sorting Engineers: O(N log N) – Sorting engineers by efficiency.
• Heap Operations: O(N log K) – Adding and removing elements from the heap.
• Overall Complexity: O(N log N + N log K).

✅ Use Cases

• Optimizing team performance in hiring scenarios
• Applications in resource allocation problems
• Efficiently processing large datasets

📘 Common LeetCode Problems

• 1383. Maximum Performance of a Team [Hard] Heap

🧪 Example: Maximum Performance of a Team

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60

Explanation:
- Select engineers with speed [10, 5] and efficiency [4, 7].
- The maximum performance is (10 + 5) * min(4, 7) = 60.

▶️ View Animation

💡 Pro Tips

• Sort engineers by efficiency to ensure the minimum efficiency is always valid.
• Use a min-heap to efficiently track the lowest speeds among the selected engineers.
• Edge cases: fewer than K engineers, engineers with identical efficiencies.