C++ Solution Explanation | priority_queue | [1792]
How priority_queue (max heap) came into picture-->\nWe have to return maximum average pass ratio which is equal to sum of all pass ratios / number of classes. W
**How priority_queue (max heap) came into picture-->**\nWe have to return maximum average pass ratio which is equal to sum of all pass ratios / number of classes. Where number of classes is constant so we need to increase the sum of all pass ratios.\nIn each class there is a pass ratio before adding extra students, as we need to increase the pass ratio of a class so we will maintain the increase in ratio if a student is added into a class.\nSuppose a class is given as [p,t], it\'s original pass ratio is p/t so initially we will add p/t to our total sum of ratios then if a student is added to this class the new ratio is (p+1)/(t+1) which means the increase in the ratio is : new ratio - old ratio which is [(p+1)/(t+1) - p/t].\nSo to maintain the profit (increase in ratio) in desc\nending order we use priority_queue here.\nAs the extra students are limited we need to add each student to the class which gives us the more profit (increase). Soon after adding the student we will increment our sum of ratios and also now the new ratio for this class will also be changed that should be added back to the queue.\n```\nclass Solution {\npublic:\n    double nextProfit(double p,double t){\n        return ((p+1)/(t+1) - p/t);\n    }\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n        double sumOfRatios = 0,p,t,profit;\n        priority_queue<pair<double,pair<double,double>>>pq;\n        for(vector<int>& v : classes){\n            p = v[0]; t = v[1];\n            sumOfRatios += p/t;\n            profit = nextProfit(p,t);\n            pq.push({profit,{p,t}});\n        }\n        pair<double,pair<double,double>>temp;\n        while(extraStudents--){\n            temp = pq.top(); pq.pop();\n            profit = temp.first; p = temp.second.first; t = temp.second.second;\n            sumOfRatios += profit;\n            p++; t++; profit = nextProfit(p,t);\n            pq.push({profit,{p,t}});\n        }\n        return (sumOfRatios/(double)classes.size());\n    }\n};\n```\nFeel free to comment your queries if any\n**Upvote** if found useful\n**Thank you :)**
['C', 'Heap (Priority Queue)']