C++ MaxHeap | No Lambda Nonsense | Comparator Class / Functor | Explained with comments
I was more familiar with Comparator Classes / Functors and completely clueless about auto []()\nSo here\'s one without Lambda functions.\n\nExplaination:\nIt is
I was more familiar with Comparator Classes / Functors and completely clueless about `auto []()`\nSo here\'s one without Lambda functions.\n\n**Explaination:**\nIt is not sufficient to pick out the class with the least pass ratio, add a brilliant kid (extraStudent), and recalculate the average. Although that might seem the best way to solve this "greedily", there may be another class which would have a greater increase/spike in the pass ratio when adding a brilliant kid (this depends on the size of the class). \n\nI define `spike` as the difference between the current Pass Ratio and the expected increase of the pass ratio in the event an `extraStudent` is added.\n\nSo all you have to do is to add a brilliant kid to the class which would have the greatest spike in the pass ratio by "sorting" the Max heap of `studentClasses` with respect to the spike/impact. The class with the highest spike is the one we\'d want to greedily add a student to.\n\n```\n// Trust me this isn\'t Java Lol\nclass studentClass {\npublic:\n    int total,passed; // total strength of the class and number of students that passed\n    double passRatio; \n\tdouble expectedIncreaseInPassRatio; // incase an extraStudent / brilliant kid is added\n    studentClass(int passed, int total)\n    {\n        this->passed = passed;\n        this->total = total;\n        passRatio = (double)passed/total;\n        expectedIncreaseInPassRatio = (double)(passed+1)/(total+1); // If an extra studen were to be added\n    }\n};\n\n// The following class helps the priorty queue in prioritizing its elements\nclass PassRatioComparator {\npublic:\n\t// This as good as passing a comparator into a built in sorting function\n    bool operator()(studentClass a, studentClass b) // Overloading the fucntion `()` operator. This is called a Fucntion Object or a Functor.\n    {\n        double spikeA = a.expectedIncreaseInPassRatio -  a.passRatio;\n        double spikeB = b.expectedIncreaseInPassRatio -  b.passRatio;\n        return spikeA < spikeB; \n\t\t// ^^ This makes sure that the class with Highest spike is infront of the Priority queue\n    }\n};\n\nclass Solution {\npublic:\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n        priority_queue<studentClass, vector<studentClass>, PassRatioComparator> maxHeap;\n        // ^^ Standard way of declaring a max heap with a comparator class \n        \n        for(auto c: classes)\n        {\n            studentClass x(c[0],c[1]); \n            maxHeap.push(x);\n        }\n        \n        while(extraStudents--)\n        {\n            studentClass x = maxHeap.top(); \n\t\t\t// ^^ This class has the highest spike/impact on adding an extra student\n            maxHeap.pop();\n            studentClass y(x.passed+1,x.total+1); \n\t\t\t// ^^ So create a new class with one extra student. \n\t\t\t\n\t\t\t// Now y has a better pass ratio such that:\n\t\t\t// y.passRatio == x.expectedIncreaseInPassRatio\n            \n            maxHeap.push(y);\n        }\n        \n        int n = maxHeap.size();\n        double sum=0;\n        while(maxHeap.size()>0)\n        {\n            sum+=maxHeap.top().passRatio;\n            maxHeap.pop();\n        }\n        return sum/n;\n    }\n};\n```\nThis is my first ever post on Leetcode Discussions.\nUpvote for more!
['Greedy', 'C', 'Heap (Priority Queue)']