Priority Queue | Greedy | C++ | Easy Solution | Comments
Explaination:\nOur goal is to maximize average. So, we should add student in the class which can give us highest difference of pass ratio. To pick up highest di
### Explaination:\nOur goal is to maximize average. So, we should add student in the class which can give us highest difference of pass ratio. To pick up highest difference from given difference Priority Queue(Max Heap) is useful. \n\n### Algorithm:\n1. Add one to pass and total for each class. Calculate new pass ratio and compute difference between old pass ratio and new pass ratio for each class and push difference and class index in Priority Queue. \n2. For each new student we have to determine in which class we can include it. So take top element of Priority Queue(having max diff. b/w new pass ration and old pass ratio). Increase classes[ind][0] and classes[ind][1] by one. Compute difference as mentioned in step 1 for ind and again push difference and class index in Priority Queue.\n3. After that for each class compute pass ratio and add them into one variable. Return sum of pass ratio / number of classes.\n\n### Code:\n\nclass Solution {\npublic:\n```\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n        cout<<setprecision(5); //to set prcision upto 10^-5\n        priority_queue<pair<double,int>> pq;\n        int n=classes.size(); \n        for(int i=0;i<n;i++){\n            int num=classes[i][0];\n            int den=classes[i][1];\n            int n_num=num+1;\n            int n_den=den+1;\n            double dif=(double)(n_num*1.0/n_den)-(double)(num*1.0/den);\n            // calculating difference between old pass ratio and after adding a student pass ratio\n            pq.push(make_pair(dif,i));\n\t\t\t// pushing pass ratio and index into priority queue\n        }\n        while(extraStudents--){\n            int tind=pq.top().second;\n            int tdiff=pq.top().first;\n            // tind dontes top index or index of class having highest difference after adding a student\n            pq.pop();\n\t\t\t// poping out top pair\n            classes[tind][0]++;\n            classes[tind][1]++;\n\t\t\t// as we have decided to add a student into class with index tind we have to increase total number of students and number of students who can pass\n            int num=classes[tind][0];\n            int den=classes[tind][1];\n            int n_num=num+1;\n            int n_den=den+1;\n            double dif=(double)(n_num*1.0/n_den)-(double)(num*1.0/den);\n            // calculated difference after adding one student\n            pq.push(make_pair(dif,tind));\n            // pushing new difference to the priority queue\n        }\n        double sum=0;\n        for(int i=0;i<n;i++){\n            sum+=(double)(classes[i][0]*1.0/classes[i][1]);\n                // adding pass ration to sum variable\n            }\n        \n        return sum/n;\n    }\n};\n```\n\n### Complexity Analysis:\nSuppose there are n number of classes. So complexity of step1 is O(n).\nSuppose there are m number of students. So complexity of step2 is O(mlog(n)) because getting max element is constant time operation and insertion in heap is log(n) time operation.\nComplexity of step3 is O(n).\n\nAs 1<=n,m<=10^5\n we can take m=n.\n \n So all over complexity O(n) + O(nlog(n)) + O(n) = O(nlogn).\n \n If you like this solution please upvote :)
['Greedy', 'Heap (Priority Queue)', 'C++']