High Five

class Solution {
private:
    int numBestScores;

public:
    vector<vector<int>> calculateHighFive(vector<vector<int>>& records) {
        this->numBestScores = 5;
        map<int, priority_queue<int, vector<int>, greater<int>>> studentScores;
        for (const auto &record: records) {
            int studentId = record[0];
            int score = record[1];
            studentScores[studentId].push(score);
            if (studentScores[studentId].size() > this->numBestScores)
                studentScores[studentId].pop();
        }
        vector<vector<int>> result;
        for (auto &[id, scores]: studentScores) {
            int sum = 0;
            for (int i = 0; i < this->numBestScores; ++i) {
                sum += scores.top();
                scores.pop();
            }
            result.push_back({id, sum / this->numBestScores});
        }
        return result;
    }
};

The "High Five" problem in C++ involves calculating the average of the top five scores for each student from a list of student-score records. The provided C++ code defines a class Solution with a method calculateHighFive to solve this task.

Here's a brief solution summary:

• Use a map where each key is a student ID and each value is a priority queue (min-heap) to store the scores of the respective student.
• Iterate over each record in the input list:
  • For each student, push the score into the student's priority queue.
  • Ensure that the priority queue never holds more than five scores by popping the smallest score if the queue size exceeds five (retaining only the top scores).
• After processing all records, iterate over the map to calculate the average of the top five scores:
  • Sum the scores retrieved from the top of the priority queue.
  • Compute the average and store the result as studentId and respective average score.
• Return a list of these averages for all students.

This approach efficiently calculates and maintains only the necessary scores (top five) for each student using priority queues, ensuring optimal use of memory and processing time.

class Solution {
    private int numScores = 5;

    public int[][] topFive(int[][] results) {
        TreeMap<Integer, PriorityQueue<Integer>> scoreMap = new TreeMap<>();
        for (int[] result : results) {
            int studentId = result[0];
            int score = result[1];
            if (!scoreMap.containsKey(studentId))
                scoreMap.put(studentId, new PriorityQueue<>());
            scoreMap.get(studentId).add(score);
            if (scoreMap.get(studentId).size() > numScores)
                scoreMap.get(studentId).poll();
        }

        List<int[]> res = new ArrayList<>();

        for (int id : scoreMap.keySet()) {
            int total = 0;
            for (int i = 0; i < numScores; ++i)
                total += scoreMap.get(id).poll();
            res.add(new int[] {id, total / numScores});
        }
        int[][] resultArray = new int[res.size()][];
        return res.toArray(resultArray);
    }
}

This Java solution for the "High Five" problem calculates the average of the top five scores for each student using a TreeMap<Integer, PriorityQueue<Integer>>.

• Initialize a TreeMap called scoreMap where the key is the student ID and the value is a PriorityQueue to store the scores.
• Iterate through the input array results. For each score:
  • Check if the student ID exists in scoreMap.
  • If not, add the student ID and a new PriorityQueue to scoreMap.
  • Insert the score into the PriorityQueue. If the size of the PriorityQueue exceeds five, remove the lowest score to ensure only the top five scores are retained.
• After processing all scores, initialize a List<int[]> to store the results.
• Iterate through the entries in scoreMap, computing the average of the scores in each PriorityQueue.
  • Poll each score from the PriorityQueue and compute the sum.
  • Calculate the average and add it to the results list.
• Convert the list to an array and return.

This approach ensures the solution dynamically manages a list of top scores for each student efficiently, maintaining a constant size for the PriorityQueue. It handles varying number of scores and students seamlessly.