Maximum Average Pass Ratio

Maximum Average Pass Ratio

What is this problem about?

In this problem, you are given a 2D array classes, where each class has [pass_count, total_students]. You are also given an integer extraStudents, representing brilliant students who are guaranteed to pass. You must assign these extra students to the classes in a way that maximizes the average pass ratio across all classes. The pass ratio of a class is pass_count / total_students. The average pass ratio is the sum of all individual class ratios divided by the number of classes.

Why is this asked in interviews?

This is a phenomenal Greedy optimization problem that tests your understanding of Priority Queues (Heaps) and marginal utility. Interviewers ask it because naive logic (like "give students to the class with the lowest ratio") mathematically fails. You must evaluate the delta—the exact mathematical increase in a class's ratio if one student is added—and greedily assign students based on that delta.

Algorithmic pattern used

This problem strictly requires a Max Heap (Priority Queue) based on Marginal Gain.

1. The gain of adding 1 student to a class is: ((pass + 1.0) / (total + 1.0)) - (pass / total).
2. Create a Max Heap that stores the classes, sorted by this calculated gain in descending order.
3. Pop the class with the highest gain from the heap. Add 1 to its pass and 1 to its total. Decrement extraStudents.
4. Recalculate the new gain for this updated class and push it back into the heap.
5. Repeat until all extraStudents are assigned. Finally, sum the actual ratios of all classes in the heap and divide by the number of classes.

Example explanation

Classes: [[1, 2], [3, 5]], Extra: 1. Initial ratios: 0.500 and 0.600. Avg = 0.550. Let's calculate the gain of adding 1 student:

• Class A [1, 2]: New ratio 2/3 (0.666). Gain = 0.666 - 0.500 = 0.166.
• Class B [3, 5]: New ratio 4/6 (0.666). Gain = 0.666 - 0.600 = 0.066. The Max Heap puts Class A at the top because its gain (0.166) is higher. We give the 1 extra student to Class A. Class A becomes [2, 3]. Final ratios: 2/3 and 3/5. Avg = (0.666 + 0.600) / 2 = 0.633.

Common mistakes candidates make

The most devastating mistake is writing a custom comparator for the heap based purely on the current pass ratio (e.g., trying to boost the lowest ratio). For example, moving [99, 100] to [100, 101] yields a tiny gain, while moving [1, 2] to [2, 3] yields a massive gain. Sorting by anything other than the exact delta (marginal gain) formula will fail the test cases. Also, using integer division (1/2 = 0) instead of floating-point division (1.0/2.0 = 0.5) will completely break the math.

Interview preparation tip

When tackling the Maximum Average Pass Ratio coding problem, immediately write a helper method: double getGain(int pass, int total). This keeps your Priority Queue comparator clean. Mention to the interviewer that you are using the concept of "Marginal Utility"—choosing the option that gives the highest instantaneous return on investment for a single unit of resource.