1383. Maximum Performance of a Team

Question

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the i<sup>th</sup> engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

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

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 10<sup>9</sup><span> </span>+ 7.

Solution

排序，将所有工程师根据其效率降序排列。

此时遍历时后一个工程师的效率一定小于等于前一个工程师。

因此，此时遍历到每一个工程师，其前面所有的工程师的efficiency均大于等于其本身。
维护一个所有选取工程师的总速度ttSpd，每次计算并更新max的值。
用最小堆来维护选取的工程师速度，如果优先级队列的尺寸超过k-1，则poll掉队列内最低的速度。

Code

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        final int mod = (int) Math.pow(10, 9) + 7;
        int[][] engineer = new int[n][2];
        
        for(int i = 0; i < n; i++){
            engineer[i][0] = speed[i];
            engineer[i][1] = efficiency[i];
        }
        
        Arrays.sort(engineer, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return b[1] - a[1];
            }
        });
        
        long max = 0, ttSpd = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < n; i++){
            int s = engineer[i][0], e = engineer[i][1];
            ttSpd += s;
            max = Math.max(max, ttSpd * e);
            pq.add(s);
            if(pq.size() == k) ttSpd -= pq.poll();
        }
        
        return (int) (max % mod);
    }
}