Maximum Average Pass Ratio

We are given classes with the number of students who will pass and the total number of students, and we have some extra students who are guaranteed to pass. We need to assign the extra students to maximize the average pass ratio.

Approach

We can use a Max Heap to solve this problem. The idea is to calculate the increase in the pass ratio for each class if an extra student is assigned and push it to the Max Heap. Then, we assign the extra students to the classes where the increase in the pass ratio is maximum.

1. Calculate the Increase in Ratio: Define a function that takes the number of passed students and total students and returns the increase in the pass ratio if an extra student is added to the class.

   (\text{increase} = \frac{{\text{passed} + 1}}{{\text{total} + 1}} - \frac{{\text{passed}}}{{\text{total}}})

2. Push to Max Heap: For each class, calculate the increase in the pass ratio and push it to the Max Heap along with the current number of passed and total students.

3. Assign Extra Students: Pop from the Max Heap, increase the passed and total students by 1, recalculate the increase in the pass ratio and push back to the heap. Repeat this extraStudents times.

4. Calculate the Final Average Pass Ratio: After assigning the extra students, calculate the average pass ratio.

Code

 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

import heapq

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        # Function to calculate the increase in the pass ratio
        def ratio_increase(passed, total):
            return (passed + 1) / (total + 1) - passed / total

        # Max Heap
        max_heap = []
        for passed, total in classes:
            # Pushing the negative of the increase to use Min Heap as Max Heap
            heapq.heappush(max_heap, (-ratio_increase(passed, total), passed, total))

        # Assigning extra students
        for _ in range(extraStudents):
            increase, passed, total = heapq.heappop(max_heap)
            passed += 1
            total += 1
            heapq.heappush(max_heap, (-ratio_increase(passed, total), passed, total))

        # Calculating final average pass ratio
        avg_pass_ratio = 0
        for _, passed, total in max_heap:
            avg_pass_ratio += passed / total

        return avg_pass_ratio / len(classes)

Complexity Analysis

• Time Complexity: (O((n + k) \log n)), where (n) is the number of classes and (k) is the number of extra students.
• Space Complexity: (O(n)) for the Max Heap.