Maximum Average Pass Ratio LeetCode solution in JavaScript

1
/**
2
 * @param {number[][]} classes
3
 * @param {number} extraStudents
4
 * @return {number}
5
 */
6
class MaxHeap {
7
  constructor() {
8
    this.heap = [];
9
  }
10

11
  push(value) {
12
    this.heap.push(value);
13
    this.heapifyUp(this.heap.length - 1);
14
  }
15

16
  pop() {
17
    if (this.heap.length === 0) {
18
      return null;
19
    }
20
    if (this.heap.length === 1) {
21
      return this.heap.pop();
22
    }
23

24
    const top = this.heap[0];
25
    this.heap[0] = this.heap.pop();
26
    this.heapifyDown(0);
27

28
    return top;
29
  }
30

31
  heapifyUp(index) {
32
    while (index > 0) {
33
      const parent = Math.floor((index - 1) / 2);
34
      if (this.heap[parent][0] < this.heap[index][0]) {
35
        [this.heap[parent], this.heap[index]] = [
36
          this.heap[index],
37
          this.heap[parent],
38
        ];
39
        index = parent;
40
      } else {
41
        break;
42
      }
43
    }
44
  }
45

46
  heapifyDown(index) {
47
    const n = this.heap.length;
48
    while (true) {
49
      let largest = index;
50
      const left = 2 * index + 1;
51
      const right = 2 * index + 2;
52

53
      if (left < n && this.heap[left][0] > this.heap[largest][0]) {
54
        largest = left;
55
      }
56
      if (right < n && this.heap[right][0] > this.heap[largest][0]) {
57
        largest = right;
58
      }
59

60
      if (largest !== index) {
61
        [this.heap[index], this.heap[largest]] = [
62
          this.heap[largest],
63
          this.heap[index],
64
        ];
65
        index = largest;
66
      } else {
67
        break;
68
      }
69
    }
70
  }
71

72
  size() {
73
    return this.heap.length;
74
  }
75
}
76

77
var maxAverageRatio = function (classes, extraStudents) {
78
  const n = classes.length;
79

80
  // Helper function to calculate pass ratio increase
81
  const passRatioIncrease = (pass, total) =>
82
    (pass + 1) / (total + 1) - pass / total;
83

84
  // Initialize max heap to keep track of classes with maximum improvement
85
  const maxHeap = new MaxHeap();
86

87
  for (let j = 0; j < n; j++) {
88
    const [pass, total] = classes[j];
89
    if (pass !== total) {
90
      const increase = passRatioIncrease(pass, total);
91
      maxHeap.push([increase, j]);
92
    }
93
  }
94

95
  let totalPassRatio = 0;
96

97
  for (let j = 0; j < n; j++) {
98
    totalPassRatio += classes[j][0] / classes[j][1];
99
  }
100

101
  for (let i = 0; i < extraStudents; i++) {
102
    if (maxHeap.size() === 0) {
103
      break; // No more classes to consider
104
    }
105

106
    const [increase, maxIndex] = maxHeap.pop();
107
    const [pass, total] = classes[maxIndex];
108
    const newPass = pass + 1;
109
    const newTotal = total + 1;
110
    const newIncrease = passRatioIncrease(newPass, newTotal);
111
    const newAvg = totalPassRatio - pass / total + newPass / newTotal;
112

113
    if (newAvg <= totalPassRatio) {
114
      break; // No further improvement possible
115
    }
116

117
    totalPassRatio = newAvg;
118
    classes[maxIndex][0]++;
119
    classes[maxIndex][1]++;
120
    maxHeap.push([newIncrease, maxIndex]);
121
  }
122

123
  return totalPassRatio / n;
124
};