Maximum Average Pass Ratio

Leetcode Problem:

• Maximum Average Pass Ratio

Summary

• Given a 2D array of classes and extra students, find the maximum average pass ratio after assigning the extra students.

Approach

• We use a max heap to store the classes, where the pass ratio of each class is used as the comparison key
• We start by pushing all classes into the heap
• Then, we pop the class with the lowest pass ratio and push a new class with the increased pass ratio until we have assigned all extra students
• Finally, we calculate the average pass ratio by summing the pass ratios of all classes and dividing by the number of classes.

Complexity

• O(n log n + m log n) where n is the number of classes and m is the number of extra students

Explanation

• The time complexity of the solution is O(n log n + m log n) because we push all classes into the heap in O(n log n) time and pop the class with the lowest pass ratio in O(log n) time, and we repeat this process m times
• The space complexity is O(n) because we store all classes in the heap.

Solution Code:

struct _node{
    int pass;
    int total;
};
struct _heap{
    _node arr[100002];
    int size;
    function cmp;
    _heap(){
        size = 1;
    }
    void push(_node a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx/2], arr[idx])){
            _node t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx /= 2;
        }
    }
    _node pop(){
        _node ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j >= size) break;
            if(j+1 < size && cmp(arr[j], arr[j+1])){
                j++;
            }
            if(cmp(arr[i], arr[j])){
                _node t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};
class Solution {
public:
    _heap h;
    double getRatio(_node classs){
        double pass = classs.pass;
        double total = classs.total;
        return pass / total;
    }
    double diffRatio(_node a){
        double ratio1 = getRatio(a);
        double ratio2 = getRatio({a.pass+1, a.total+1});
        return ratio2 - ratio1;
    }
    double maxAverageRatio(vector>& classes, int extraStudents) {
        h.cmp = [&](_node a, _node b) {
            double diffRatio1 = diffRatio(a);
            double diffRatio2 = diffRatio(b);
            return diffRatio1 < diffRatio2;
        };
        for(int i = 0 ; i < classes.size(); i++){
            h.push({classes[i][0], classes[i][1]});
        }
        while(extraStudents--){
            _node clas = h.pop();
            h.push({clas.pass+1, clas.total+1});
        }
        double sum = 0;
        while(!h.empty()){
            sum += getRatio(h.pop());
        }
        return sum / classes.size();
    }
};