Lintcode 613. High Five

There are two properties in the node student id and scores, to ensure that each student will have at least 5 points, find the average of 5 highest scores for each person.

Example

Example 1:

Input: 
[[1,91],[1,92],[2,93],[2,99],[2,98],[2,97],[1,60],[1,58],[2,100],[1,61]]
Output:
1: 72.40
2: 97.40

Example 2:

Input:
[[1,90],[1,90],[1,90],[1,90],[1,90],[1,90]]
Output: 
1: 90.00

Code (Java):

/**
 * Definition for a Record
 * class Record {
 *     public int id, score;
 *     public Record(int id, int score){
 *         this.id = id;
 *         this.score = score;
 *     }
 * }
 */
public class Solution {
    /**
     * @param results a list of <student_id, score>
     * @return find the average of 5 highest scores for each person
     * Map<Integer, Double> (student_id, average_score)
     */
    public Map<Integer, Double> highFive(Record[] results) {
        // Write your code here
        if (results == null || results.length == 0) {
            return new HashMap<Integer, Double>();
        }
        
        Map<Integer, PriorityQueue<Integer>> studentToScoreMap = new HashMap<>();
        for (Record record : results) {
            PriorityQueue<Integer> pq = studentToScoreMap.getOrDefault(record.id, new PriorityQueue<>());
            pq.offer(record.score);
            if (pq.size() > 5) {
                pq.poll();
            }
            studentToScoreMap.put(record.id, pq);
        }
        
        Map<Integer, Double> ans = new HashMap<>();
        for (Integer id : studentToScoreMap.keySet()) {
            PriorityQueue<Integer> scores = studentToScoreMap.get(id);
            double ave = getAverageScore(scores);
            ans.put(id, ave);
        }
        
        return ans;
    }
    
    private double getAverageScore(PriorityQueue<Integer> scores) {
        int sum = 0;
        int numScores = scores.size();
        while (!scores.isEmpty()) {
            sum += scores.poll();
        }
        
        return (double) sum / numScores;
    }
}