Leetcode # 1792. Maximum Average Pass Ratio

Problem

https://leetcode.com/problems/maximum-average-pass-ratio

Solution: Priority Queue

Priority Queue 裡面要放甚麼？

the pass ratios
the number of total students
the gains in the pass ratio

Code

Time Complexity: O(log(len(classes)) * extraStudents)
Space Complexity: O(len(classes))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxAverageRatio( \
      self, classes: List[List[int]], \
      extraStudents: int) -> float:
    gains = \
        [[-((p + 1) / (t + 1) - p / t), i] \
        for i, (p, t) in enumerate(classes)]
    heapify(gains)

    for _ in range(extraStudents):
      gr, i = gains[0]
      classes[i][0] += 1
      classes[i][1] += 1
      new_gain = \
          -((classes[i][0] + 1) / (classes[i][1] + 1) \
          - classes[i][0] / classes[i][1])
      heappushpop(gains, [new_gain, i])

    return sum([p / t for p, t in classes]) / len(classes)

Last Updated on 2024/12/15 by A1go