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 协议》,转载必须注明作者和本文链接