Maximum Performance of a Team - Practice Coding Problems

Maximum Performance of a Team - Problem

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 i-th 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 10⁹ + 7.

Input & Output

Example 1 — Basic Case

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

› Output: 60

💡 Note: We choose engineers 2 and 5 (0-indexed) with speeds [10,5] and efficiencies [4,7]. Performance = (10+5) × min(4,7) = 15 × 4 = 60.

Example 2 — Single Engineer

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

› Output: 68

💡 Note: Choose engineer with efficiency 9 and speed 1, plus top 2 others by speed considering efficiency constraint. Best combination gives performance 68.

Example 3 — All Engineers

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

› Output: 72

💡 Note: When k equals n, we can consider all engineers. The optimal team maximizes sum of speeds × minimum efficiency across all possible combinations.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ speed[i] ≤ 10⁵
1 ≤ efficiency[i] ≤ 10⁸
1 ≤ k ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input

Engineers with speed and efficiency values, team size k

Process

Find optimal team that maximizes sum of speeds × minimum efficiency

Output

Maximum performance value modulo 10^9 + 7

Key Takeaway

🎯 Key Insight: Sort by efficiency descending, then greedily pick top k speeds using a min-heap to try every possible minimum efficiency

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to sort engineers by efficiency in descending order, then for each engineer as the minimum efficiency, greedily select the top k speeds using a min-heap. This ensures we consider every possible minimum efficiency while maintaining optimal speed selection. Best approach uses greedy with heap. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Sorting and Heap	O(n log n)	O(n)	Sort by efficiency descending, use min-heap to maintain top k speeds
Brute Force - Try All Combinations	O(2ⁿ × n)	O(n)	Generate all possible teams of size 1 to k and calculate performance for each

Greedy with Sorting and Heap — Algorithm Steps

Sort engineers by efficiency descending
Initialize min-heap for speeds
For each engineer as min efficiency:
Add current speed to heap
If heap size > k, remove minimum speed
Calculate performance and track maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Efficiency

Arrange engineers by efficiency descending

Process Each Engineer

Add speed to heap, maintain top k speeds

Calculate Performance

Use current efficiency as minimum, sum of heap as speeds

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int efficiency;
    int speed;
} Engineer;

typedef struct {
    int* data;
    int size;
    int capacity;
} MinHeap;

MinHeap* createHeap(int capacity) {
    MinHeap* heap = malloc(sizeof(MinHeap));
    heap->data = malloc(capacity * sizeof(int));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void heapPush(MinHeap* heap, int val) {
    int idx = heap->size++;
    heap->data[idx] = val;
    
    // Bubble up
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (heap->data[parent] <= heap->data[idx]) break;
        int temp = heap->data[parent];
        heap->data[parent] = heap->data[idx];
        heap->data[idx] = temp;
        idx = parent;
    }
}

int heapPop(MinHeap* heap) {
    if (heap->size == 0) return 0;
    int result = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    
    // Bubble down
    int idx = 0;
    while (1) {
        int minIdx = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (left < heap->size && heap->data[left] < heap->data[minIdx]) {
            minIdx = left;
        }
        if (right < heap->size && heap->data[right] < heap->data[minIdx]) {
            minIdx = right;
        }
        
        if (minIdx == idx) break;
        int temp = heap->data[idx];
        heap->data[idx] = heap->data[minIdx];
        heap->data[minIdx] = temp;
        idx = minIdx;
    }
    
    return result;
}

int compareEngineers(const void* a, const void* b) {
    Engineer* ea = (Engineer*)a;
    Engineer* eb = (Engineer*)b;
    return eb->efficiency - ea->efficiency; // Descending order
}

long long solution(int n, int* speed, int* efficiency, int k) {
    const long long MOD = 1000000007LL;
    
    // Create engineers array
    Engineer* engineers = malloc(n * sizeof(Engineer));
    for (int i = 0; i < n; i++) {
        engineers[i].efficiency = efficiency[i];
        engineers[i].speed = speed[i];
    }
    
    // Sort by efficiency descending
    qsort(engineers, n, sizeof(Engineer), compareEngineers);
    
    long long maxPerformance = 0;
    long long speedSum = 0;
    MinHeap* speedHeap = createHeap(k + 1);
    
    for (int i = 0; i < n; i++) {
        speedSum += engineers[i].speed;
        heapPush(speedHeap, engineers[i].speed);
        
        if (speedHeap->size > k) {
            speedSum -= heapPop(speedHeap);
        }
        
        long long performance = (speedSum * engineers[i].efficiency) % MOD;
        if (performance > maxPerformance) {
            maxPerformance = performance;
        }
    }
    
    free(engineers);
    free(speedHeap->data);
    free(speedHeap);
    return maxPerformance;
}

int main() {
    int n, k;
    scanf("%d", &n);
    
    int* speed = malloc(n * sizeof(int));
    int* efficiency = malloc(n * sizeof(int));
    
    // Read speed array
    char line[1000];
    scanf(" %s", line);
    char* token = strtok(line + 1, ",]");
    for (int i = 0; i < n; i++) {
        speed[i] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Read efficiency array
    scanf(" %s", line);
    token = strtok(line + 1, ",]");
    for (int i = 0; i < n; i++) {
        efficiency[i] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    scanf("%d", &k);
    
    printf("%lld\n", solution(n, speed, efficiency, k));
    
    free(speed);
    free(efficiency);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), heap operations are O(log k) for n iterations

⚡ Linearithmic

Space Complexity

O(n)

Space for sorted array and heap of size at most k

⚡ Linearithmic Space

156.0K Views

Medium Frequency

~35 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Sorting and Heap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler