DDSA Solutions

1792. Maximum Average Pass Ratio

MediumView on LeetCode
GreedyHeap (Priority Queue)Probability & Statistics

Problem Overview

Maximize average pass ratio by greedily adding extra students to the class that benefits most.

Intuition

Maximize average pass ratio by greedily adding extra students to the class that benefits most. Use max-heap by gain.

Algorithm

  1. 1Gain of adding to class (pass, total) = (pass+1)/(total+1) - pass/total.
  2. 2Max-heap by gain. For each extra student: pop max gain class, add student, push back.
  3. 3Sum all pass/total ratios at end.

Common Pitfalls

  • •Use max-heap by marginal gain. Each extra student goes to class with highest current marginal gain.
1792.cs
C#
// Approach: Max-heap keyed by marginal gain of adding one student; greedily assign all extra students.
// Time: O((n+e) log n) Space: O(n)

public class Solution
{
    public double MaxAverageRatio(int[][] classes, int extraStudents)
    {
        // (extra pass ratio, pass, total)
        PriorityQueue<T, double> maxHeap = new PriorityQueue<T, double>();

        foreach (var c in classes)
        {
            int pass = c[0];
            int total = c[1];
            maxHeap.Enqueue(new T(GetExtraPassRatio(pass, total), pass, total),
                             -GetExtraPassRatio(pass, total));
        }

        for (int i = 0; i < extraStudents; ++i)
        {
            int pass = maxHeap.Peek().Pass;
            int total = maxHeap.Dequeue().Total;
            maxHeap.Enqueue(new T(GetExtraPassRatio(pass + 1, total + 1), pass + 1, total + 1),
                               -GetExtraPassRatio(pass + 1, total + 1));
        }

        double ratioSum = 0;

        while (maxHeap.Count > 0)
            ratioSum += (double)maxHeap.Peek().Pass / maxHeap.Dequeue().Total;

        return ratioSum / classes.Length;
    }

    // Returns the extra pass ratio if a brilliant student joins.
    private double GetExtraPassRatio(int pass, int total)
    {
        return (pass + 1) / (double)(total + 1) - pass / (double)total;
    }

    private record T(double ExtraPassRatio, int Pass, int Total);
}
Was this solution helpful?

Related Problems