# https://leetcode.com/problems/maximum-average-pass-ratio/
# 1792. Maximum Average Pass Ratio

# History:
# 1.
# Jul 18, 2021

# There is a school that has classes of students and each class will be having a final exam.
# You are given a 2D integer array classes, where classes[i] = [passi, totali].
# You know beforehand that in the ith class, there are totali total students,
# but only passi number of students will pass the exam.
#
# You are also given an integer extraStudents. There are another extraStudents brilliant students that are
# guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents
# students to a class in a way that maximizes the average pass ratio across all the classes.
#
# The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the
# total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided
# by the number of the classes.
#
# Return the maximum possible average pass ratio after assigning the extraStudents students.
# Answers within 10-5 of the actual answer will be accepted.
#
#
#
# Example 1:
#
# Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
# Output: 0.78333
# Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal
# to (3/4 + 3/5 + 2/2) / 3 = 0.78333.
# Example 2:
#
# Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
# Output: 0.53485
#
#
# Constraints:
#
# 1 <= classes.length <= 105
# classes[i].length == 2
# 1 <= passi <= totali <= 105
# 1 <= extraStudents <= 105

from heapq import heappop, heappush


class Solution(object):
    def _calculate_diff(self, c):
        return c[0] / float(c[1]) - (c[0] + 1) / float(c[1] + 1), c

    def maxAverageRatio(self, classes, extraStudents):
        """
        :type classes: List[List[int]]
        :type extraStudents: int
        :rtype: float
        """
        hp = []
        for c in classes:
            heappush(hp, self._calculate_diff(c))

        for student in range(extraStudents):
            nxt = heappop(hp)
            heappush(hp, self._calculate_diff([nxt[1][0] + 1, nxt[1][1] + 1]))

        return sum([c[1][0] / float(c[1][1]) for c in hp]) / float(len(hp))
