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 Average Pass Ratio

Number: 1917

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given an array of classes where each class is represented as [pass, total] and an integer extraStudents, assign each extra student (who is guaranteed to pass) to a class in order to maximize the overall average pass ratio. The pass ratio for a class is defined as pass/total and the overall average is the sum of all pass ratios divided by the number of classes.

Key Insights

  • Assigning an extra student increases both pass and total for that class.
  • The benefit (or delta) from adding an extra student is not uniform; it depends on the current pass and total in that class.
  • The delta for adding a student to class (p, t) is computed as: Delta = (p + 1) / (t + 1) - p / t.
  • A greedy approach is effective: always allocate an extra student to the class with the maximum improvement (largest delta).
  • Use a max heap (priority queue) to efficiently retrieve the class with the largest delta at each step.

Space and Time Complexity

Time Complexity: O(extraStudents * log n), where n is the number of classes, since each extra student assignment involves a push and pop operation on the heap. Space Complexity: O(n) for maintaining the heap.

Solution

The solution uses a greedy algorithm combined with a max heap (priority queue). For every class, calculate the improvement in pass ratio (delta) if an extra student is added. Insert each class into the max heap with its delta as the key. Then, while there are extra students available, pop the class with the largest delta, update its pass and total numbers, recompute the new delta, and push it back into the heap. Finally, compute the average pass ratio across all classes.

Key Data Structures and Techniques:

  • Priority Queue/Heap: Used to always select the class where the next extra student has the maximum impact.
  • Greedy algorithm: At each step, greedily assign an extra student to the class that yields the maximum improvement.
  • Delta Calculation: The improvement from adding an extra student in a given class which is computed as (p+1)/(t+1) - (p/t).

Code Solutions

import heapq

def maxAverageRatio(classes, extraStudents):
    # Function to calculate the improvement in pass ratio if one extra student is added
    def delta(pass_count, total):
        return (pass_count + 1) / (total + 1) - pass_count / total

    # Create a max heap by storing negative delta values (to simulate max heap)
    heap = []
    for p, t in classes:
        # Calculate the initial delta for each class
        heapq.heappush(heap, (-delta(p, t), p, t))
    
    # Assign extra students to the class with the maximum delta
    for _ in range(extraStudents):
        d, p, t = heapq.heappop(heap)
        p += 1
        t += 1
        # Push the updated class with new delta back into the heap
        heapq.heappush(heap, (-delta(p, t), p, t))
    
    total_ratio = 0
    # Sum pass ratios for all classes in the heap
    while heap:
        d, p, t = heapq.heappop(heap)
        total_ratio += p / t
    
    # Compute the average pass ratio
    return total_ratio / len(classes)

# Example usage:
print(maxAverageRatio([[1,2],[3,5],[2,2]], 2))  # Expected output ~0.78333
← Back to All Questions