1383. Maximum Performance of a Team

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers. 

 

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

 

Constraints:

  • 1 <= n <= 10^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^8
  • 1 <= k <= n

Rust Solution

struct Solution;

use std::cmp::Reverse;
use std::collections::BinaryHeap;

const MOD: i64 = 1_000_000_007;

impl Solution {
    fn max_performance(n: i32, speed: Vec<i32>, efficiency: Vec<i32>, k: i32) -> i32 {
        let n = n as usize;
        let k = k as usize;
        let mut max_efficiency: BinaryHeap<(i32, i32)> = BinaryHeap::new();
        for i in 0..n {
            max_efficiency.push((efficiency[i], speed[i]));
        }
        let mut min_speed: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
        let mut sum_speed = 0;
        let mut res = 0;
        while let Some((e, s)) = max_efficiency.pop() {
            sum_speed += s as i64;
            min_speed.push(Reverse(s));
            if min_speed.len() > k {
                sum_speed -= min_speed.pop().unwrap().0 as i64;
            }
            res = res.max(sum_speed as i64 * e as i64);
        }
        (res % MOD) as i32
    }
}

#[test]
fn test() {
    let n = 6;
    let speed = vec![2, 10, 3, 1, 5, 8];
    let efficiency = vec![5, 4, 3, 9, 7, 2];
    let k = 2;
    let res = 60;
    assert_eq!(Solution::max_performance(n, speed, efficiency, k), res);
    let n = 6;
    let speed = vec![2, 10, 3, 1, 5, 8];
    let efficiency = vec![5, 4, 3, 9, 7, 2];
    let k = 3;
    let res = 68;
    assert_eq!(Solution::max_performance(n, speed, efficiency, k), res);
    let n = 6;
    let speed = vec![2, 10, 3, 1, 5, 8];
    let efficiency = vec![5, 4, 3, 9, 7, 2];
    let k = 4;
    let res = 72;
    assert_eq!(Solution::max_performance(n, speed, efficiency, k), res);
}

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