1383. Maximum Performance of a Team

题目详见:1383. Maximum Performance of a Team

解法一

思路
代码
class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        int[][] se = new int[n][2]; // Combine speed and efficiency together

        for (int i = 0; i < n; i++) {
            se[i] = new int[]{speed[i], efficiency[i]};
        }

        // Sort the array in desc order according to the efficiency
        Arrays.sort(se, (a, b) -> b[1] - a[1]); 
        PriorityQueue<Integer> pq = new PriorityQueue<>(k, (a, b) -> a - b); // Store k speed

        long max = 0, currSum = 0; 
        for (int[] e : se) {
            pq.offer(e[0]); // Add speed into pq
            currSum += e[0];
            if (pq.size() > k) currSum -= pq.poll();
            max = Math.max(max, currSum * e[1]);
        }

        return (int) (max % (long)(1e9 + 7));
    }
}
复杂度分析
  • 时间复杂度
  • 空间复杂度
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!