We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Performance of a Team

Number: 1499

Difficulty: Hard

Paid? No

Companies: Amazon, DE Shaw, Flipkart, TikTok, Citrix

Problem Description

Given n engineers, each with a speed and an efficiency value, choose at most k engineers to form a team. The team's performance is defined as the sum of the chosen engineers’ speeds multiplied by the minimum efficiency among them. The goal is to maximize the team performance, and the result must be returned modulo 10^9 + 7.

Key Insights

  • Sort the engineers by efficiency in descending order so that when processing an engineer, their efficiency is the minimum for the current selection.
  • Use a min-heap to maintain the top speeds among the selected engineers. This helps in efficiently removing the engineer with the smallest speed when the team exceeds k members.
  • Keep a running sum of the speeds currently in the team.
  • At each iteration, calculate the potential performance as the current speed sum multiplied by the current engineer’s efficiency (which is the minimum efficiency for the team so far) and update the maximum performance if it is higher.

Space and Time Complexity

Time Complexity: O(n log k)
Space Complexity: O(k)

Solution

The solution involves the following steps:

  1. Pair each engineer’s speed and efficiency then sort these pairs in descending order based on efficiency.
  2. Initialize a min-heap (or priority queue) to store speeds and a variable to keep the running sum of speeds.
  3. Iterate through the sorted engineers. For each engineer:
    • Add the engineer’s speed to the min-heap and update the running sum.
    • If the size of the heap exceeds k, remove the smallest speed from the heap and subtract it from the running sum.
    • Compute the current performance as the running sum multiplied by the current engineer's efficiency.
    • Update the maximum performance if the current performance is greater.
  4. Return the maximum performance modulo 10^9 + 7.

Using a min-heap ensures that when the team size exceeds k, the smallest speed can be removed in O(log k) time, keeping the overall complexity efficient.

Code Solutions

import heapq

def maxPerformance(n, speed, efficiency, k):
    MOD = 10**9 + 7
    # Create pairs of (efficiency, speed) and sort by efficiency descending
    engineers = sorted(zip(efficiency, speed), key=lambda x: -x[0])
    
    max_perf = 0      # Store maximum performance encountered
    speed_sum = 0     # Running sum of speeds in the current team
    speed_heap = []   # Min-heap for the speeds in the team

    # Iterate through each engineer sorted by descending efficiency
    for curr_eff, curr_speed in engineers:
        # Add current engineer's speed to the heap
        heapq.heappush(speed_heap, curr_speed)
        speed_sum += curr_speed
        
        # If there are more than k engineers, remove the one with the smallest speed
        if len(speed_heap) > k:
            speed_sum -= heapq.heappop(speed_heap)
        
        # Calculate team performance with current engineer as minimum efficiency
        curr_perf = speed_sum * curr_eff
        max_perf = max(max_perf, curr_perf)
    
    return max_perf % MOD

# Example usage:
print(maxPerformance(6, [2,10,3,1,5,8], [5,4,3,9,7,2], 2))
← Back to All Questions