Problem Description
There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes
, where classes[i] = [passi, totali]
. You know beforehand that in the ith
class, there are totali
total students, but only passi
number of students will pass the exam.
You are also given an integer extraStudents
. There are another extraStudents
brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents
students to a class in a way that maximizes the average pass ratio across all the classes.
The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.
Return the maximum possible average pass ratio after assigning the extraStudents
students. Answers within 10-5
of the actual answer will be accepted.
Example 1:
Input: classes = [[1,2],[3,5],[2,2]],
extraStudents
= 2 Output: 0.78333 Explanation: 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
Constraints:
1 <= classes.length <= 105
classes[i].length == 2
1 <= passi <= totali <= 105
1 <= extraStudents <= 105
Difficulty: Medium
Tags: array, greedy, heap (priority queue)
Rating: 91.70%
Solution Approach
The key insight is that we should assign each extra student to the class where they’ll make the biggest improvement in the overall average. This naturally leads to a greedy approach using a max heap.
Algorithm:
- Create a max heap ordered by potential improvement
- For each extra student:
- Take the class with maximum potential improvement
- Add the student to that class
- Recalculate and reinsert the updated class
- Calculate final average pass ratio
Detailed Example
Let’s walk through Example 1: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Initial state:
Class 1: 1/2 = 0.500 (improvement if added: 2/3 - 1/2 = 0.167)
Class 2: 3/5 = 0.600 (improvement if added: 4/6 - 3/5 = 0.067)
Class 3: 2/2 = 1.000 (improvement if added: 3/3 - 2/2 = 0.000)
Steps:
-
First student goes to Class 1 (maximum improvement):
Class 1: 2/3 = 0.667 (new improvement: 3/4 - 2/3 = 0.083) Class 2: 3/5 = 0.600 (improvement: 4/6 - 3/5 = 0.067) Class 3: 2/2 = 1.000 (improvement: 3/3 - 2/2 = 0.000)
-
Second student also goes to Class 1:
Class 1: 3/4 = 0.750 Class 2: 3/5 = 0.600 Class 3: 2/2 = 1.000
Final average: (0.750 + 0.600 + 1.000) / 3 = 0.783
Python Implementation
class Solution:
def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
def improvement(pass_count, total):
"""Calculate improvement in pass ratio if we add one student"""
return (pass_count + 1)/(total + 1) - (pass_count/total)
# Create max heap (using negative values since heapq is min heap)
heap = []
for p, t in classes:
imp = improvement(p, t)
heappush(heap, (-imp, p, t))
# Assign each extra student
for _ in range(extraStudents):
imp, p, t = heappop(heap)
# Calculate new improvement after adding a student
new_imp = improvement(p + 1, t + 1)
heappush(heap, (-new_imp, p + 1, t + 1))
# Calculate final average
return sum(p/t for _, p, t in heap) / len(classes)
Complexity Analysis
- Time Complexity: , where:
- N is the number of classes
- E is the number of extra students
- Each heap operation is O(log N)
- Space Complexity: for the heap
Key Insights
- Greedy Choice Property: Adding a student to the class with the highest potential improvement is optimal at each step
- Heap Usage: Max heap efficiently gives us the class with maximum improvement potential
. Improvement Formula: The improvement calculation
(p+1)/(t+1) - p/t
captures the marginal benefit of adding one student