[Python] 100% Efficient solution, easy to understand with comments and explanation
Key Idea: We need to keep assigning the remaining extra students to the class which can experience the greatest impact. \n\nLet see an example below, if we have
**Key Idea:** We need to keep assigning the remaining extra students to the class which can experience the greatest impact. \n\nLet see an example below, if we have following clasess - [[2,4], [3,9], [4,5], [2,10]], then the impact of assignment students to each class can be defined as,\n\n```\n# In simple terms it can be understood as follows,\n\ncurrentRatio = passCount/totalCount\nexpectedRatioAfterUpdate = (passCount+1)/(totalCount+1)\nimpact = expectedRatioAfterUpdate - currentRatio\n\t\t\t\nOR\n\n# Formula to calculate impact of assigning a student to a class\nimpacts[i] = (classes[i][0]+1) / (classes[i][1]+1) - classes[i][0]/classes[i][1]\ni.e.\nimpacts[0] -> (4+1)/(2+1)-4/2 \nimpacts[1] -> (3+1)/(9+1)-3/9 \n.\n.\netc.\n```\n\nAnd, once we assign a student to a class, then we need the class with "next" greatest impact. We know that heap is perfect candidate for scenarios in which you need to pick the least/greatest of all the collections at any point of time.\n\nHence, we can leverage that to fetch the greatest impacts in all the cases. \n\n**Note:** in below code we have negated (observe `-` sign ), because by default python heaps are min heaps. Hence, it\'s sort of a workaround to make our logic work :)\n\n```\nclass Solution:\n\tdef maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n\t\t\n\t\tn = len(classes)\n\t\t\n\t\timpacts = [0]*n\n\t\tminRatioIndex = 0\n\t\t\n\t\t# calculate and store impacts for each class in form of tuples -> (-impactValue, passCount, totalCount)\n\t\tfor i in range(n):\n\t\t\tpassCount = classes[i][0]\n\t\t\ttotalCount = classes[i][1]\n\t\t\t\n\t\t\t# calculate the impact  for class i\n\t\t\tcurrentRatio = passCount/totalCount\n\t\t\texpectedRatioAfterUpdate = (passCount+1)/(totalCount+1)\n\t\t\timpact = expectedRatioAfterUpdate - currentRatio\n\t\t\t\n\t\t\timpacts[i] = (-impact, passCount, totalCount)  # note the - sign for impact\n\t\t\t\n\t\theapq.heapify(impacts)\n\t\t\n\t\twhile(extraStudents > 0):\n\t\t\t# pick the next class with greatest impact \n\t\t\t_, passCount, totalCount = heapq.heappop(impacts)\n\t\t\t\n\t\t\t# assign a student to the class\n\t\t\tpassCount+=1\n\t\t\ttotalCount+=1\n\t\t\t\n\t\t\t# calculate the updated impact  for current class\n\t\t\tcurrentRatio = passCount/totalCount\n\t\t\texpectedRatioAfterUpdate = (passCount+1)/(totalCount+1)\n\t\t\timpact = expectedRatioAfterUpdate - currentRatio\n\t\t\t\n\t\t\t# insert updated impact back into the heap\n\t\t\theapq.heappush(impacts, (-impact, passCount, totalCount))\n\t\t\textraStudents -= 1\n\t\t\n\t\tresult = 0\n\t\t\t\n\t\t# for all the updated classes calculate the total passRatio \n\t\tfor _, passCount, totalCount in impacts:\n\t\t\tresult += passCount/totalCount\n\t\t\t\n\t\t# return the average pass ratio\n\t\treturn result/n\n```
['Heap (Priority Queue)', 'Python', 'Python3']