Maximum Average Pass Ratio LeetCode solution in Python

1
class Solution:
2
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
3

4
        n = len(classes)
5

6
        impacts = [0] * n
7
        minRatioIndex = 0
8

9
        # calculate and store impacts for each class in form of tuples -> (-impactValue, passCount, totalCount)
10
        for i in range(n):
11
            passCount = classes[i][0]
12
            totalCount = classes[i][1]
13

14
            # calculate the impact  for class i
15
            currentRatio = passCount / totalCount
16
            expectedRatioAfterUpdate = (passCount + 1) / (totalCount + 1)
17
            impact = expectedRatioAfterUpdate - currentRatio
18

19
            impacts[i] = (-impact, passCount, totalCount)  # note the - sign for impact
20

21
        heapq.heapify(impacts)
22

23
        while extraStudents > 0:
24
            # pick the next class with greatest impact
25
            _, passCount, totalCount = heapq.heappop(impacts)
26

27
            # assign a student to the class
28
            passCount += 1
29
            totalCount += 1
30

31
            # calculate the updated impact  for current class
32
            currentRatio = passCount / totalCount
33
            expectedRatioAfterUpdate = (passCount + 1) / (totalCount + 1)
34
            impact = expectedRatioAfterUpdate - currentRatio
35

36
            # insert updated impact back into the heap
37
            heapq.heappush(impacts, (-impact, passCount, totalCount))
38
            extraStudents -= 1
39

40
        result = 0
41

42
        # for all the updated classes calculate the total passRatio
43
        for _, passCount, totalCount in impacts:
44
            result += passCount / totalCount
45

46
        # return the average pass ratio
47
        return result / n