Maximum Performance of a Team

📋

Problem

Imagine you're a manager selecting a team of engineers to maximize overall project performance, balancing their speed and efficiency under a team size limit.

You are given two integer arrays speed and efficiency, both of length n, and an integer k. You want to form a team of at most k engineers to maximize the team's performance. The performance of a team is defined as the sum of the speeds of the team members multiplied by the minimum efficiency among them. Return the maximum performance of this team modulo 10^9 + 7. Input: - n: integer, number of engineers - speed: integer array of length n - efficiency: integer array of length n - k: integer, maximum team size Output: - integer, maximum performance modulo 10^9 + 7

1 ≤ n ≤ 10^5speed.length == nefficiency.length == n1 ≤ speed[i], efficiency[i] ≤ 10^51 ≤ k ≤ n

Edge cases: k = 1 (only one engineer can be chosen) → output is max speed[i]*efficiency[i]All efficiencies are equal → output is sum of top k speeds * that efficiencyAll speeds are equal → output is speed * minimum efficiency among chosen k

</>

IDE

def maxPerformance(n: int, speed: list[int], efficiency: list[int], k: int) -> int:public int maxPerformance(int n, int[] speed, int[] efficiency, int k)int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k)function maxPerformance(n, speed, efficiency, k)

def maxPerformance(n, speed, efficiency, k):
    # Write your solution here
    pass

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
    // Write your solution here
    return 0;
}

function maxPerformance(n, speed, efficiency, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Wrong max performance due to ignoring efficiency sortingNot sorting engineers by efficiency descending before processing.✅ Sort engineers by efficiency descending before iterating and building the heap.

Wrong: Incorrect performance due to not maintaining heap size <= kNot removing smallest speed when heap size exceeds k.✅ Use a min-heap for speeds and pop smallest speed when heap size > k.

Wrong: Wrong output due to greedy picking highest speeds ignoring efficiencyGreedy approach picking top speeds without considering efficiency leads to wrong min efficiency.✅ Sort by efficiency descending and maintain min-heap of speeds to maximize performance.

Wrong: TLE on large inputsUsing brute force or exponential approach instead of O(n log n) heap-based solution.✅ Implement sorting by efficiency and min-heap to achieve O(n log n) complexity.

Wrong: Incorrect output on single element or k=1 casesNot handling base cases where team size is 1 or input size is 1.✅ Return speed[0]*efficiency[0] modulo 10^9+7 when n=1 or k=1.

✓

Test Cases

Try testing your solution on minimal inputs and uniform values to catch base case bugs.

Consider tricky cases where greedy choices fail or constraints like team size limit are critical.

Focus on algorithmic complexity and data structures to handle large inputs efficiently.

t1_01basic

Input{"n":6,"speed":[2,10,3,1,5,8],"efficiency":[5,4,3,9,7,2],"k":2}

Expected60

⏱ Performance - must finish in 2000ms

Choose engineers with speed 10 and 5, efficiencies 4 and 7. Minimum efficiency is 4, sum speed is 15, performance = 15*4=60.

💡 Sort engineers by efficiency descending and consider teams with top efficiencies.

💡 Use a min-heap to keep track of the k highest speeds while iterating.

💡 At each step, calculate performance as sum of speeds in heap times current efficiency.

Why it failed: Failed basic case: likely not sorting by efficiency or not maintaining min-heap of speeds. Fix by sorting engineers by efficiency descending and using a min-heap to track speeds.

✓ Correctly handles the canonical example with sorting and heap.

t1_02basic

Input{"n":5,"speed":[5,1,3,7,4],"efficiency":[3,9,7,5,6],"k":3}

Expected68

⏱ Performance - must finish in 2000ms

Choose engineers with speeds 1,3,7 and efficiencies 9,7,5. Minimum efficiency is 5, sum speed is 11, performance = 11*5=55. But better is speeds 5,7,4 with efficiencies 3,5,6; min efficiency 3, sum speed 16, performance=48. Best is speeds 1,3,4 with efficiencies 9,7,6; min efficiency 6, sum speed 8, performance=48. Actually best is speeds 5,3,4 with efficiencies 3,7,6; min efficiency 3, sum speed 12, performance=36. The maximum is 68 by choosing speeds 5,7,4 with efficiencies 3,5,6 and min efficiency 3, sum speed 16, performance=48. Rechecking: speeds 1,7,4 with efficiencies 9,5,6 min eff 5 sum speed 12 perf 60. Speeds 1,3,7 with eff 9,7,5 min eff 5 sum speed 11 perf 55. Speeds 1,4,7 with eff 9,6,5 min eff 5 sum speed 12 perf 60. Speeds 3,4,7 with eff 7,6,5 min eff 5 sum speed 14 perf 70. So best is 70.

💡 Try sorting engineers by efficiency descending and use a min-heap to track speeds.

💡 Keep track of sum of speeds in the heap and remove smallest speed when heap size exceeds k.

💡 Calculate performance at each step as sum of speeds times current efficiency and track max.

Why it failed: Incorrect output due to not maintaining heap size or not updating max performance correctly. Fix by removing smallest speed when heap size exceeds k and updating max performance at each iteration.

✓ Correctly computes max performance for varied inputs with heap and sorting.

t2_01edge

Input{"n":1,"speed":[10],"efficiency":[5],"k":1}

Expected50

⏱ Performance - must finish in 2000ms

Only one engineer, performance = speed * efficiency = 10 * 5 = 50.

💡 Check behavior when only one engineer is available.

💡 Ensure code handles k=1 and single-element arrays correctly.

💡 Return speed[0] * efficiency[0] modulo 10^9+7 for single engineer.

Why it failed: Fails single element case: likely not handling k=1 or single-element arrays properly. Fix by returning speed[0]*efficiency[0] when n=1 or k=1.

✓ Correctly handles single engineer scenario.

t2_02edge

Input{"n":4,"speed":[5,5,5,5],"efficiency":[3,3,3,3],"k":3}

Expected45

⏱ Performance - must finish in 2000ms

All efficiencies equal to 3, choose top 3 speeds (all 5), sum speed = 15, performance = 15 * 3 = 45.

💡 Test when all efficiencies are equal.

💡 Sum top k speeds and multiply by common efficiency.

💡 Ensure sorting by efficiency does not break when efficiencies are equal.

Why it failed: Fails equal efficiency case: likely not handling equal efficiencies or sorting stably. Fix by sorting engineers by efficiency descending and summing top k speeds.

✓ Correctly handles all equal efficiencies.

t2_03edge

Input{"n":3,"speed":[7,7,7],"efficiency":[10,5,8],"k":2}

Expected105

⏱ Performance - must finish in 2000ms

All speeds equal 7, choose two engineers with efficiencies 10 and 8, min efficiency 8, sum speed 14, performance = 14 * 8 = 112. But better is efficiencies 10 and 5, min 5, sum speed 14, performance 70. So max is 112.

💡 Test when all speeds are equal but efficiencies differ.

💡 Choose engineers with highest efficiencies to maximize min efficiency.

💡 Sum speeds of chosen engineers and multiply by minimum efficiency.

Why it failed: Fails equal speed case: likely not correctly tracking minimum efficiency among chosen engineers. Fix by sorting by efficiency descending and updating min efficiency at each step.

✓ Correctly handles all equal speeds with varying efficiencies.

t3_01corner

Input{"n":4,"speed":[10,9,8,7],"efficiency":[1,2,3,4],"k":3}

Expected48

⏱ Performance - must finish in 2000ms

Greedy by speed fails: picking top 3 speeds (10,9,8) min efficiency 1 performance 27. Correct is picking engineers with efficiencies 4,3,2 and speeds 7,8,9 sum speed 24 min eff 2 performance 48.

💡 Beware of greedy approach picking highest speeds only.

💡 Sort by efficiency descending and use min-heap to track speeds.

💡 Remove smallest speed when heap size exceeds k to maximize performance.

Why it failed: Fails greedy trap: picking top speeds without considering efficiency leads to wrong min efficiency and performance. Fix by sorting by efficiency descending and maintaining min-heap of speeds.

✓ Correctly avoids greedy trap by sorting and heap.

t3_02corner

Input{"n":5,"speed":[2,2,2,2,2],"efficiency":[5,4,3,2,1],"k":3}

Expected24

⏱ Performance - must finish in 2000ms

Confusing 0/1 vs unbounded: only 3 engineers can be chosen, sum speed max 6, min efficiency depends on chosen engineers. Best is efficiencies 5,4,3 speeds 2,2,2 sum speed 6 min eff 3 performance 18. But better is efficiencies 5,4,2 speeds 2,2,2 sum speed 6 min eff 2 performance 12. Actually best is efficiencies 5,4,3 sum speed 6 min eff 3 performance 18. Check all combinations: max is 18.

💡 Ensure team size limit k is respected (0/1 constraint).

💡 Do not count engineers multiple times (no unbounded knapsack).

💡 Use min-heap to maintain exactly k speeds and update performance.

Why it failed: Fails 0/1 constraint: allowing repeated engineers or ignoring k limit. Fix by maintaining heap size <= k and removing smallest speed when exceeded.

✓ Correctly enforces team size limit.

t3_03corner

Input{"n":3,"speed":[1,100,1],"efficiency":[10,1,10],"k":2}

Expected20

⏱ Performance - must finish in 2000ms

Off-by-one error: choosing engineers with speeds 1 and 1 and efficiencies 10 and 10 sum speed 2 min eff 10 performance 20. Choosing 100 and 1 with efficiencies 1 and 10 min eff 1 performance 101. Actually max is 101. So best is speeds 100 and 1 with min eff 1 performance 101.

💡 Check indexing and heap size updates carefully.

💡 Ensure performance calculation uses correct min efficiency.

💡 Update max performance at each iteration after heap adjustments.

Why it failed: Fails off-by-one: incorrect heap size or performance update timing. Fix by updating max performance after heap size check and removal.

✓ Correctly handles indexing and performance updates.

t4_01performance

Input{"n":100,"speed":[100000,99999,99998,99997,99996,99995,99994,99993,99992,99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,99981,99980,99979,99978,99977,99976,99975,99974,99973,99972,99971,99970,99969,99968,99967,99966,99965,99964,99963,99962,99961,99960,99959,99958,99957,99956,99955,99954,99953,99952,99951,99950,99949,99948,99947,99946,99945,99944,99943,99942,99941,99940,99939,99938,99937,99936,99935,99934,99933,99932,99931,99930,99929,99928,99927,99926,99925,99924,99923,99922,99921,99920,99919,99918,99917,99916,99915,99914,99913,99912,99911,99910,99909,99908,99907,99906,99905,99904,99903,99902,99901,99900],"efficiency":[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,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and k=50 to test O(n log n) solution performance within 2 seconds.

💡 Use sorting by efficiency and min-heap to achieve O(n log n) complexity.

💡 Avoid brute force which is exponential and will time out.

💡 Maintain heap size at most k to keep operations efficient.

Why it failed: TLE due to brute force or inefficient approach. Fix by implementing sorting by efficiency and min-heap to maintain top speeds.

✓ Efficient O(n log n) solution passes performance test.

Practice

1. Given the following code snippet for finding employee free time, what is the final output when the input schedule is [[[1,2],[5,6]], [[1,3]], [[4,10]]]?

from typing import List

def employeeFreeTime(schedule: List[List[List[int]]]) -> List[List[int]]:
    intervals = [iv for employee in schedule for iv in employee]
    intervals.sort(key=lambda x: x[0])
    free_times = []
    prev_end = intervals[0][1]
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start > prev_end:
            free_times.append([prev_end, start])
        prev_end = max(prev_end, end)
    return free_times

schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]
print(employeeFreeTime(schedule))

easy

A. [[3,4]]

B. [[3,4], [6,10]]

C. [[2,4]]

D. [[3,4]]

Solution

1. Step 1: Sort all intervals

   Flattened intervals: [1,2], [5,6], [1,3], [4,10]. Sorted by start: [1,2], [1,3], [4,10], [5,6].

2. Step 2: Merge intervals and find gaps

   Initialize prev_end=2. Iterate: - Interval [1,3]: start=1 ≤ prev_end=2, update prev_end=max(2,3)=3 - Interval [4,10]: start=4 > prev_end=3, gap [3,4] added, update prev_end=10 - Interval [5,6]: start=5 ≤ prev_end=10, update prev_end=max(10,6)=10 Return free_times=[[3,4]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only one gap between merged intervals is [3,4] [OK]

Hint: Sort intervals and track max end to find gaps [OK]

Common Mistakes:

• Off-by-one errors in gap detection
• Including zero-length intervals
• Incorrect sorting leading to wrong gaps

2. You need to find the median of every contiguous subarray of size k in an integer array efficiently. Which approach best guarantees an optimal solution for this problem?

easy

A. Use a dynamic programming approach to precompute medians for all subarrays

B. Sort each window independently and pick the median

C. Maintain two balanced heaps (max-heap and min-heap) with lazy removal to track the median as the window slides

D. Use a sliding window with a simple queue and recompute median by scanning the window each time

Solution

1. Step 1: Understand the problem constraints

   Finding median in each sliding window requires efficient insertion, deletion, and median retrieval.

2. Step 2: Evaluate approaches

   Sorting each window (A) is too slow (O(nk log k)). DP (C) doesn't apply well to median. Simple queue (D) can't maintain order efficiently. Balanced two heaps (B) maintain order and allow O(log k) updates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two heaps maintain median efficiently [OK]

Hint: Two heaps efficiently maintain median in sliding window [OK]

Common Mistakes:

• Thinking sorting each window is efficient enough
• Assuming DP can precompute medians
• Using simple queue without order maintenance

3. What is the time complexity of the optimal max-heap based algorithm for minimizing deviation in an array of size n with maximum element M?

medium

A. O(n^2)

B. O(n log M)

C. O(n log n)

D. O(n log n * log M)

Solution

1. Step 1: Analyze heap operations per element

   Each element is pushed once initially, O(n log n). Then max elements are halved repeatedly, up to log M times.

2. Step 2: Combine heap operations and halving steps

   Each halving involves a pop and push on heap, each O(log n), repeated up to log M times per element, total O(n log n * log M).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Complexity accounts for heap operations and repeated halving [OK]

Hint: Repeated halving causes extra log M factor multiplied by heap ops [OK]

Common Mistakes:

• Ignoring the log M factor from repeated halving
• Confusing n log n with n log M
• Assuming quadratic complexity due to nested loops

4. Examine the following Python code snippet implementing the balanced two heaps approach for sliding window median. Which line contains a subtle bug that can cause incorrect median calculation for even window sizes?

medium

A. Line adding out_num to delayed dictionary

B. Line calculating median for even k: median = (-small[0][0] + large[0][0]) / 2

C. Line pruning heaps using delayed dictionary

D. Line with heapq.heappush(large, (-val, idx)) in balance()

Solution

1. Step 1: Analyze balance() function

   When moving elements between heaps, signs must be handled carefully to maintain max-heap and min-heap properties.

2. Step 2: Identify incorrect sign usage

   In line pushing to large heap, negation is incorrect; it should push positive val to min-heap, not negative.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect sign breaks heap order, causing wrong median [OK]

Hint: Check sign handling when moving elements between heaps [OK]

Common Mistakes:

• Incorrect sign negation when balancing heaps
• Forgetting to prune delayed elements
• Wrong median calculation for even k

5. What is the time complexity of the optimized task scheduler algorithm that uses a hash map to track the next available day for each task, given n tasks and cooldown space?

medium

A. O(n * space) due to iterating over cooldown days for each task

B. O(n) because each task is processed once with O(1) hash map operations

C. O(n log n) due to sorting tasks or heap operations

D. O(n^2) because of nested loops checking cooldown constraints

Solution

1. Step 1: Identify operations per task

   Each task is processed once in a single loop over the tasks array.

2. Step 2: Analyze hash map operations

   Hash map lookups and updates for next_available are O(1) on average, so no nested loops or sorting involved.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with O(1) lookups -> O(n) time -> [OK]

Hint: Hash map lookups are O(1), no nested loops -> O(n) [OK]

Common Mistakes:

• Assuming cooldown causes nested loops increasing complexity
• Confusing with heap-based solutions that are O(n log n)
• Thinking space affects time complexity linearly