Java || PriorityQueue || O(mlogn+nlogn)
\n\t// O(mlogn+nlogn)\n\t// PriorityQueue\n\tpublic double maxAverageRatio(int[][] classes, int extraStudents) {\n\n\t\tPriorityQueue heap = new PriorityQueue(n
\n\t// O(m*logn+n*logn)\n\t// PriorityQueue\n\tpublic double maxAverageRatio(int[][] classes, int extraStudents) {\n\n\t\tPriorityQueue<double[]> heap = new PriorityQueue<double[]>(new Comparator<double[]>() {\n\t\t\t@Override\n\t\t\tpublic int compare(double[] o1, double[] o2) {\n\t\t\t\treturn Double.compare(o2[0], o1[0]);\n\t\t\t}\n\t\t});\n\t\tfor (int[] clas : classes) {\n\t\t\tdouble delta = profit(clas[0], clas[1]);\n\t\t\theap.offer(new double[] { delta, clas[0], clas[1] });\n\t\t}\n\n\t\twhile (extraStudents >= 1) {\n\t\t\tdouble[] temp = heap.poll();\n\t\t\tdouble pass = temp[1] + 1, total = temp[2] + 1;\n\t\t\tdouble delta = profit(pass, total);\n\t\t\theap.offer(new double[] { delta, pass, total });\n\t\t\textraStudents--;\n\t\t}\n\n\t\tdouble average = 0d;\n\t\twhile (!heap.isEmpty()) {\n\t\t\tdouble[] temp = heap.poll();\n\t\t\taverage += temp[1] / temp[2];\n\t\t}\n\n\t\treturn average / classes.length;\n\t}\n\n\t// O(1)\n\tpublic double profit(double a, double b) {\n\t\treturn (a + 1) / (b + 1) - a / b;\n\t}\n
[]