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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Average Pass Ratio

Difficulty: Medium

Problem Description

You are given a 2D integer array classes, where classes[i] = [pass_i, total_i], indicating that in the i-th class, pass_i students will pass the exam out of total_i students. You also have extraStudents, which are guaranteed to pass any class they are assigned to. The goal is to assign these extra students to maximize the average pass ratio across all classes.

Key Insights

  • The pass ratio of a class is defined as the number of students passing divided by the total number of students in that class.
  • Assigning extra students to classes with a lower current pass ratio can yield a higher increase in overall average pass ratio.
  • A greedy approach using a max-heap can efficiently determine which class to assign the next extra student to based on the potential increase in pass ratio.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of classes. This accounts for sorting the classes and using a priority queue (heap) for managing class selection. Space Complexity: O(n), primarily for storing the classes and the heap.

Solution

To solve the problem, we will:

  1. Calculate the initial pass ratio for each class.
  2. Use a max-heap (priority queue) to keep track of the classes based on the potential increase in their pass ratios when an extra student is added.
  3. For each extra student, we will pop the class with the highest potential increase from the heap, assign the student, and push the updated class back into the heap.
  4. Finally, compute the average pass ratio after all students have been assigned.

Data Structures Used

  • A max-heap (priority queue) is used to efficiently retrieve and update the class with the highest potential increase in pass ratio.

Code Solutions

import heapq

def maxAverageRatio(classes, extraStudents):
    def potential_increase(pass_count, total_count):
        # Calculate the potential increase in ratio if one extra student passes
        return (pass_count + 1) / (total_count + 1) - pass_count / total_count
    
    # Create a max-heap based on the potential increase
    max_heap = []
    
    for pass_count, total_count in classes:
        increase = potential_increase(pass_count, total_count)
        # Push negative increase to simulate max-heap using min-heap
        heapq.heappush(max_heap, (-increase, pass_count, total_count))
    
    # Distribute the extra students
    for _ in range(extraStudents):
        # Pop the class with the highest potential increase
        neg_increase, pass_count, total_count = heapq.heappop(max_heap)
        pass_count += 1  # Assign an extra student
        total_count += 1
        # Push back the updated class
        new_increase = potential_increase(pass_count, total_count)
        heapq.heappush(max_heap, (-new_increase, pass_count, total_count))
    
    # Calculate the final average pass ratio
    total_pass_ratio = 0
    for _, pass_count, total_count in max_heap:
        total_pass_ratio += pass_count / total_count
    
    return total_pass_ratio / len(classes)
← Back to All Questions