[Python] Greedy Heap
\n\nhtml5\n<b>Time Complexity: O((m+n)&middot;log(n))</b> where m = extraStudents and n = classes.length &becaus; we perform m operations on a length n heap\n<b
\n\n```html5\n<b>Time Complexity: O((m+n)&middot;log(n))</b> where m = extraStudents and n = classes.length &becaus; we perform m operations on a length n heap\n<b>Space Complexity: O(n)</b> &becaus; every class must be stored in the heap.\n```\n\n**Approach:**\n\nGreedily select the most needy class to receive a brilliant student.\nThe most needy class will be the class whose ratio increases the\nmost by giving it a brilliant student.\n\n>i.e. 5/10 = 50% and 10/20 = 50% but the first class will \n>benefit more because 6/11 = 54.5% and 11/21 = 52.4%\n\nStore all of the classes and their neediness in a heap so that the\nmost needy class is at `h[0]`.\n\nThen pop the most needy class, give it a brilliant student and update the heap.\nRepeat this step `m` times for `m` brilliant students and return the average class ratio.\n\n<hr>\n\n```python\nclass Solution:\n    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n        \n        # 1. Heapify classes according to how much they will benefit from getting a brilliant student\n        h = []\n        for p, t in classes:\n            delta = ((p+1) / (t+1)) - (p / t)\n            heapq.heappush(h, (-delta, p, t))\n        \n        # 2. Pop the most needy class and give it a brilliant student\n        #    Then insert the class back into the heap.\n        for _ in range(extraStudents):\n            d, p, t = heapq.heappop(h)\n            p += 1\n            t += 1\n            delta = ((p+1) / (t+1)) - (p / t)\n            heapq.heappush(h, (-delta, p, t))\n            \n        total_ratio = sum(p/t for d, p, t in h)\n        return total_ratio / len(h)\n```
[]