[LintCode] Problem 613 - High Five

Posted on | In ,

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

No.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

No.2

Input:
[[1,90],[1,90],[1,90],[1,90],[1,90],[1,90]]

Output:
1: 90.00

Code

1
2
3
4
5
6
7
public class Record {
    public int id, score;
    public Record(int id, int score){
        this.id = id;
        this.score = score;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public Map<Integer, Double> highFive(Record[] results) {
    Map<Integer, Double> avgHigh = new HashMap<>();
    PriorityQueue<Record> queue = new PriorityQueue<>(new Comparator<Record>() {
        @Override
        public int compare(Record o1, Record o2) {
            if (o1.id != o2.id)
                return o1.id - o2.id;

            return o2.score - o1.score;
        }
    });

    for (Record record : results)
        queue.offer(record);

    int id = Integer.MIN_VALUE;
    int sum = 0;

    while (!queue.isEmpty()) {
        if (queue.peek().id != id) {
            id = queue.peek().id;

            for (int i = 0; i < 5; i++) {
                Record record = queue.poll();
                sum += record.score;
            }

            avgHigh.put(id, (double) sum / 5);
            sum = 0;
        }

        while (!queue.isEmpty() && queue.peek().id == id)
            queue.poll();
    }

    return avgHigh;
}