1086. High Five

Given a list of the scores of different students, items, where items[i] = [IDi, scorei] represents one score from a student with IDi, calculate each student's top five average.

Return the answer as an array of pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average. Sort result by IDj in increasing order.

A student's top five average is calculated by taking the sum of their top five scores and dividing it by 5 using integer division.

 

Example 1:

Input: items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
Output: [[1,87],[2,88]]
Explanation: 
The student with ID = 1 got scores 91, 92, 60, 65, 87, and 100. Their top five average is (100 + 92 + 91 + 87 + 65) / 5 = 87.
The student with ID = 2 got scores 93, 97, 77, 100, and 76. Their top five average is (100 + 97 + 93 + 77 + 76) / 5 = 88.6, but with integer division their average converts to 88.

Example 2:

Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]

 

Constraints:

  • 1 <= items.length <= 1000
  • items[i].length == 2
  • 1 <= IDi <= 1000
  • 0 <= scorei <= 100
  • For each IDi, there will be at least five scores.

Rust Solution

struct Solution;
use std::cmp::Reverse;
use std::collections::BTreeMap;
use std::collections::BinaryHeap;

impl Solution {
    fn high_five(items: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut btm: BTreeMap<i32, (BinaryHeap<Reverse<i32>>, i32)> = BTreeMap::new();
        let mut res = vec![];
        for item in items {
            let id = item[0];
            let score = item[1];
            let (pq, sum) = btm.entry(id).or_default();
            pq.push(Reverse(score));
            *sum += score;
            if pq.len() > 5 {
                *sum -= pq.pop().unwrap().0;
            }
        }
        for (id, (_, sum)) in btm {
            res.push(vec![id, sum / 5]);
        }
        res
    }
}

#[test]
fn test() {
    let items = vec_vec_i32![
        [1, 91],
        [1, 92],
        [2, 93],
        [2, 97],
        [1, 60],
        [2, 77],
        [1, 65],
        [1, 87],
        [1, 100],
        [2, 100],
        [2, 76]
    ];
    let res = vec_vec_i32![[1, 87], [2, 88]];
    assert_eq!(Solution::high_five(items), res);
}

Having problems with this solution? Click here to submit an issue on github.