The CHEATCODE to solving this problem!
IntuitionWe have an integer extraStudents to disperse among classes. Naturally, while we still have an extraStudent we want to assign them to the class that wil
# Intuition\nWe have an integer *extraStudents* to disperse among classes. Naturally, while we still have an *extraStudent* we want to assign them to the class that will benefit the most. \n\nBut how do we know which class will benefit most? There is no obvious greedy heuristic that works. Here is where the CHEAT comes in, we don\'t need a greedy strategy to inform us which class will benefit most. We can just compute ourselves. Calculate the difference between a classes ratio after adding an extra student vs before. This is objectively how much the ratio will increase if a student is added.\n\nNow that we know how to determine which class will benefit most we should consider how to find the class that will benefit most after each extra student is added. \n\nIn essense we just need to find the min of all class ratios. This is a common pattern. It can be done effeceintly using a heap to find the min in logarithmic time.\n\n# Approach\n\nFirst compute the initial ratio gain each class will have from adding an extra student (ie. (passing+1/total+1) / (passing/total)). We will use this as the index of our heap. We negate it because heap is a min heap by default (this way biggest ratio gain becomes the min element). We also store the current counts of passing and total students per class so we can update the ratio gain if we add an additonal student to the class.\n\nAssigning extra students will never decrease the average ratio so we want to assign all of them. Thus we iterate for each extra student. We find the top of the heap (the class with the most to gain) and add a student. We the push the class back on the heap with an updated ratio, pass, and total counts.\n\nOnce we have iterated for all extra students we simply compute the average of the ratios by iterating through our list of classes, computing the ratios, summing them, and diving by the number of classes.\n\n# Complexity\n- Time complexity:\nO(Elog(c))\n\n- Space complexity:\nO(C)\n\n# Code\n```python3 []\nclass Solution:\n    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n        ratios = [(-(((x+1)/(y+1))-(x/y)), x, y) for x, y in classes]\n        heapify(ratios)\n        for _ in range(extraStudents):\n            mn = heappop(ratios)\n            heappush(ratios, (-(((mn[1]+2)/(mn[2]+2)-(mn[1]+1)/(mn[2]+1))), mn[1] + 1, mn[2] + 1))\n        return sum([x/y for _, x, y in ratios]) / len(ratios)\n```
['Greedy', 'Heap (Priority Queue)', 'Python3']