Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The objective is the sum of class pass ratios divided by a fixed class count. One added passing student improves a class by (p + 1)/(t + 1) - p/t. That gain decreases as more students join the same class, so repeatedly choosing the largest current marginal gain is optimal.

Approach

Build a max-priority heap of each class's gain and pass/total counts; Python negates gains to use a min-heap. For every extra student, pop the best class, increase both counts, recompute its next gain, and push it back. Finally sum the updated ratios and divide by the number of classes. Classes already at a perfect ratio have zero gain and need no special handling.

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        def con(p, t):
            curr = p / t
            new_pr = (p + 1) / (t + 1)
            return new_pr - curr

        h = []

        for p, t in classes:
            h.append((-con(p, t), p, t))

        # max heap
        heapq.heapify(h)

        for _ in range(extraStudents):
            _, p, t = heapq.heappop(h)
            heapq.heappush(h, (-con(p + 1, t + 1), p + 1, t + 1))

        res = 0

        for _, p, t in h:
            res += p / t

        return res / len(classes)

Complexity analysis

For c classes and e extra students, heap construction and the final average take O(c) time. The e heap updates take O(e log(c + 1)), including O(e) when c = 1. Total time is O(c + e log(c + 1)), and auxiliary heap space is O(c).