Python  |  Greedy Algorithm Pattern  &  Priority Queue (Heap)
see the Successfully Accepted SubmissionCodeKey InsightsImpact of an Extra StudentAdding one extra student to a class will increase its pass ratio. The key is t
[see the Successfully Accepted Submission](https://leetcode.com/problems/maximum-average-pass-ratio/submissions/1478957269/?envType=daily-question&envId=2024-12-15)\n\n# Code\n```python3 []\nclass Solution:\n    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n        # Function to calculate the gain in pass ratio for adding a student to a class\n        def pass_ratio_gain(passi, totali):\n            return (passi + 1) / (totali + 1) - passi / totali\n        \n        # Max-heap to store the gain, -gain because heapq is a min-heap by default\n        heap = []\n        for passi, totali in classes:\n            gain = pass_ratio_gain(passi, totali)\n            heappush(heap, (-gain, passi, totali))\n        \n        # Distribute the extra students\n        for _ in range(extraStudents):\n            # Pop the class with the maximum gain\n            gain, passi, totali = heappop(heap)\n            # Add one student to this class\n            passi += 1\n            totali += 1\n            # Recalculate gain and push back into heap\n            new_gain = pass_ratio_gain(passi, totali)\n            heappush(heap, (-new_gain, passi, totali))\n        \n        # Calculate the final average pass ratio\n        total_ratio = 0\n        for _, passi, totali in heap:\n            total_ratio += passi / totali\n        \n        return total_ratio / len(classes)\n\n```\n\n# Key Insights\n\n## Impact of an Extra Student\nAdding one extra student to a class will increase its pass ratio. The key is to calculate the **gain in pass ratio** when an extra student is added to a class. This can help prioritize which class should get the next extra student.\n\n## Priority Queue (Max-Heap)\nTo efficiently determine which class benefits the most from an extra student, use a **max-heap** where the priority is the gain in pass ratio for adding an extra student to a class.\n\n\n\n## Iterative Allocation\n1. Start by calculating the **initial gain** for all classes and insert them into the heap.\n2. Iteratively assign the extra students to the class with the **maximum gain**, updating the heap as you go.\n\n# Explanation of Code\n\n## Heap Initialization\n1. Compute the gain for each class and insert it into the max-heap.\n2. Store \\(-\\text{gain}\\) because Python\'s `heapq` is a min-heap, and we need max behavior.\n\n## Allocate Extra Students\n1. Extract the class with the **highest potential gain**.\n2. Add one extra student to this class and recalculate its gain.\n3. Reinsert the updated class into the heap.\n\n## Compute Average\nAfter distributing all extra students, compute the final average pass ratio by:\n1. Summing the pass ratios of all classes.\n2. Dividing by the total number of classes.\n\n# Complexity\n\n## Heap Operations\n- **Push and Pop Operations**: Each push and pop from the heap takes \\(O(\\log k)\\), where \\(k\\) is the number of classes.\n\n## Total Time\n- **Initial Heap Construction**: \\(O(k \\log k)\\).\n- **Extra Student Allocation**: \\(O(n \\log k)\\), where \\(n\\) is the number of extra students.\n- **Overall Time Complexity**: \\(O((n + k) \\log k)\\).\n\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)\n
['Python3']