#1792

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Average Pass Ratio

Maximize the average pass ratio by assigning extra guaranteed-passing students using a greedy heap strategy for optimal allocation.

array greedy heap priority queue

Problem Statement

A school has multiple classes, each with a number of students and an expected number of passes. You are given a 2D array classes, where classes[i] = [passi, totali], indicating that out of totali students, passi will pass the final exam. You are also given an integer extraStudents representing brilliant students guaranteed to pass any class they join. Your task is to assign these extra students to classes to maximize the average pass ratio.

The pass ratio of a class is passi divided by totali. The average pass ratio is the sum of all class pass ratios divided by the number of classes. Return the maximum possible average pass ratio after assigning all extraStudents optimally. Precision errors within 1e-5 are acceptable.

Examples

Example 1

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2

Output: 0.78333

You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2

Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4

Output: 0.53485

Example details omitted.

Constraints

1 <= classes.length <= 105
classes[i].length == 2
1 <= passi <= totali <= 105
1 <= extraStudents <= 105

Solution Approach

Compute initial ratios and potential gains

For each class, calculate the current pass ratio passi/totali. Then compute the potential increase in pass ratio if one extra student is added: (passi+1)/(totali+1) - passi/totali. This gain determines which class benefits most from an extra student.

Use a max-heap to assign extra students greedily

Push all classes into a max-heap keyed by their potential gain from adding one extra student. Repeatedly pop the class with the highest gain, increment passi and totali by one, recalculate its gain, and push it back. Continue until all extraStudents are assigned.

Calculate final average pass ratio

After assigning all extra students, sum the final pass ratios of all classes and divide by the number of classes. This yields the maximum achievable average pass ratio. Floating point precision should be handled carefully to avoid rounding errors.

Complexity Analysis

Metric	Value
Time	O(k \cdot \log(n) + n)
Space	O(n)

Time complexity is O(k \cdot \log(n) + n), where k is extraStudents and n is number of classes due to heap operations for each assignment. Space complexity is O(n) for storing the heap and class states.

What Interviewers Usually Probe

Look for correct greedy selection by evaluating marginal gain for each class.
Check heap usage for efficient selection of the class with the maximum potential increase.
Ensure correct floating-point handling and avoid integer division errors.

Common Pitfalls or Variants

Common pitfalls

Not recalculating the gain after each student assignment can lead to suboptimal choices.
Assigning extra students without using a heap or priority queue may exceed time limits for large inputs.
Ignoring floating-point precision may cause the output to fail strict test cases.

Follow-up variants

Assigning extra students but minimizing the average failure ratio instead of maximizing pass ratio.
Weighted classes where some classes contribute more to the average, modifying the greedy choice.
Limited extraStudents per class, requiring a modified heap strategy to respect per-class limits.

FAQ

What is the best approach to maximize average pass ratio?

Use a greedy strategy with a max-heap, always assigning the next extra student to the class where it increases the pass ratio most.

Why use a heap for this problem?

A heap efficiently tracks which class currently benefits the most from an extra student, reducing time complexity compared to scanning all classes repeatedly.

How is the pass ratio defined for each class?

The pass ratio is the number of passing students divided by the total number of students in the class, i.e., passi/totali.

Can floating-point precision affect the output?

Yes, since results are compared within 1e-5 tolerance, careful floating-point arithmetic is required to pass strict test cases.

Does this problem fit the greedy choice plus invariant validation pattern?

Exactly. Each assignment improves the overall average, maintaining the invariant that every extra student contributes maximally, illustrating the classic greedy selection pattern.

terminal

Solution

Solution 1: Priority Queue (Max-Heap of Increment)

Suppose a class currently has a pass rate of $\frac{a}{b}$. If we arrange a smart student into this class, then the pass rate of the class will become $\frac{a+1}{b+1}$. We can find that the increment of the pass rate is $\frac{a+1}{b+1} - \frac{a}{b}$.

1

2

3

4

5

6

7

8

9

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
        heapify(h)
        for _ in range(extraStudents):
            _, a, b = heappop(h)
            a, b = a + 1, b + 1
            heappush(h, (a / b - (a + 1) / (b + 1), a, b))
        return sum(v[1] / v[2] for v in h) / len(classes)

Continue Practicing

#1705 maximum number of eaten apples #1686 stone game vi #1675 minimize deviation in array