Description
有
n個工程師，第 i 個工程師有速度speed[i]和效率efficiency[i]。從中最多選k個工程師組成團隊，團隊表現 = 所選工程師速度總和 * 所選工程師效率最小值。回傳最大可能的團隊表現，結果對 10^9 + 7 取模。
Example:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2 Output: 60
Intuition#
核心思路：依效率降序排序，遍歷時當前效率為最小值，用 Min Heap 維護速度最大的 k 個以最大化總和。
- 表現 = sum(speed) * min(efficiency)
- 如果固定 min(efficiency)，希望 sum(speed) 最大化
- 依效率降序遍歷，每個工程師的效率都可能是團隊的最小效率
- 用 Min Heap 維護最大的 k 個 speed，超過 k 個時彈出最小的
- 注意：是「最多 k 個」不是「恰好 k 個」，但依效率降序遍歷，加入更多人 speed 總和更大，效率更低，所以正好 k 個時的乘積不一定最大，需要每次都計算
Approaches#
⭐1: Sorting + Min Heap#
- 概念: 依效率降序排序，遍歷時用 Min Heap 維護最大 k 個 speed，計算每個可能的表現值
- 時間複雜度:
O(n log n)- 排序 + heap 操作 - 空間複雜度:
O(n)
class Solution {
fun maxPerformance(n: Int, speed: IntArray, efficiency: IntArray, k: Int): Int {
val MOD = 1_000_000_007L
val indices = (0 until n).sortedByDescending { efficiency[it] }
val minHeap = PriorityQueue<Int>()
var speedSum = 0L
var result = 0L
for (idx in indices) {
minHeap.offer(speed[idx])
speedSum += speed[idx]
if (minHeap.size > k) {
speedSum -= minHeap.poll()
}
result = maxOf(result, speedSum * efficiency[idx])
}
return (result % MOD).toInt()
}
}🔑 Takeaways#
- Pattern: 「乘積 = 總和 * 最小值」→ 依最小值降序排序，Heap 維護最大總和
- 關鍵技巧: 與 2542. Maximum Subsequence Score 同一 pattern，但此題是「最多 k 個」而非「恰好 k 個」，不過在降序遍歷中，每次都計算結果即可涵蓋所有情況；注意取模只在最後回傳時做