[Python3] Heap solution with explanation
\u2018Assign each of the extraStudents students to a class to maximize the average pass ratio across all the classes\u2019 \n-> For each extraStudents find pair
- \u2018Assign each of the extraStudents students to a class to maximize the average pass ratio across all the classes\u2019 \n-> For each extraStudents find pair [pass, total] where **increase = (pass + 1) / (total + 1) - pass / total** maximum.\n\n- The idea is using a max heap to maintain pair [pass, total] with max increase.\n\n```\nExample: classes = [[1,2],[3,5],[2,2]], extraStudents = 2\nWith first student:\n\t* \tincrease = [0.16666, 0.06666, 0] -> Choose class (1, 2)\n\t\tmax_heap = [(-0.16666, 1, 2), (-0.06666, 3, 5), (-0.0, 2, 2)] \n\tIf you wonder why store (-increase) instead of increase, the reason is Python only support min_heap and -min_heap is a max_heap.\n\n\t* \tAt # 1: Pop (-0.16666, 1, 2) and add increase to total_increase\n\n\t* \tAt # 2: After assign 1 extraStudents to class (1, 2), class will be (2, 3). \n\tPush it again to max_heap: (-0.08333, 2, 3) and continue with second student.\n```\t\t\n\n\n\n```\nclass Solution:\n    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n        N = len(classes)\n        ini_pass = 0\n        total_increase = 0\n        \n        max_heap = []\n        for p, c in classes:\n\t\t\t# Calculate total pass ratio at first\n            ini_pass += p / c\n\t\t\t\n\t\t\t# Store increase pass ratio to max_heap\n            increase = (p + 1) / (c + 1) - p / c\n            heappush(max_heap, (-increase, p, c))\n        \n        while extraStudents:\n\t\t\t# Pop the pair with max increase\n            increase, p, c = heappop(max_heap)\t\t\t# 1\n            total_increase -= increase\n\t\t\t\n\t\t\t# Push the pair to max_heap again\n            p, c = p + 1, c + 1\n            increase = (p + 1) / (c + 1) - p / c\n            heappush(max_heap, (-increase, p, c))\t\t# 2\n                        \n            extraStudents -= 1\n        \n        return (ini_pass + total_increase) / N\n```
[]