To maximize the average pass ratio, I approached the problem using a greedy strategy. The key idea is that each time I assign a brilliant student to a class, the benefit to the average pass ratio depends on how much that student increases the pass ratio of the chosen class. For a class with p passing students out of t total, the gain from adding one more passing student is (p+1)/(t+1) - p/t. This value decreases as more students are added to the same class, so it’s optimal to always assign the next student to the class with the current largest gain. To implement this efficiently, I used a max-heap (priority queue) where each entry stores the negative of the gain (since Python’s heapq is a min-heap) along with the class data. I repeatedly popped the class with the best gain, updated its values by adding one student, recomputed its gain, and pushed it back. After all extra students were assigned, I computed the final average by summing p/t for each class and dividing by the number of classes.
class Solution:
def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
def gain(p: int, t: int) -> float:
return (p + 1) / (t + 1) - p / t
heap = []
for p, t in classes:
heapq.heappush(heap, (-gain(p, t), p, t))
for _ in range(extraStudents):
g, p, t = heapq.heappop(heap)
p, t = p + 1, t + 1
heapq.heappush(heap, (-gain(p, t), p, t))
total = 0.0
while heap:
_, p, t = heapq.heappop(heap)
total += p / t
return total / len(classes)- Time: O((n+extraStudents)logn) — build heap 𝑂 ( 𝑛 ) O(n), each assignment is a pop+push.
- Space: O(n)
