有
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
TIP
核心思路：依效率降序排序，遍歷時當前效率為最小值，用 Min Heap 維護速度最大的 k 個以最大化總和。
- 表現 = sum(speed) * min(efficiency)
- 如果固定 min(efficiency)，希望 sum(speed) 最大化
- 依效率降序遍歷，每個工程師的效率都可能是團隊的最小效率
- 用 Min Heap 維護最大的 k 個 speed，超過 k 個時彈出最小的
- 注意：是「最多 k 個」不是「恰好 k 個」，但依效率降序遍歷，加入更多人 speed 總和更大，效率更低，所以正好 k 個時的乘積不一定最大，需要每次都計算
Approaches
1. Brute Force: Fix Min Efficiency, Top-k Speeds in Prefix — O(n² log n) / O(n)
- Idea: 依效率降序，對每個工程師當「最小效率」，在其前綴中取速度最大的 k 個求和
- Time:
O(n² log n)- 每個 i 排序前綴速度 - Space:
O(n)
class Solution {
fun maxPerformance(n: Int, speed: IntArray, efficiency: IntArray, k: Int): Int {
val MOD = 1_000_000_007L
val order = (0 until n).sortedByDescending { efficiency[it] }
var ans = 0L
for (i in order.indices) {
val speeds = ArrayList<Int>()
for (j in 0..i) speeds.add(speed[order[j]])
speeds.sortDescending()
var sum = 0L
for (t in 0 until minOf(k, speeds.size)) sum += speeds[t]
ans = maxOf(ans, sum * efficiency[order[i]])
}
return (ans % MOD).toInt()
}
}⭐ 2. Sorting + Min Heap — O(n log n) / O(n)
- Idea: 依效率降序排序，遍歷時用 Min Heap 維護最大 k 個 speed，計算每個可能的表現值
- Time:
O(n log n)- 排序 + heap 操作 - Space:
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 維護最大總和
- Key trick: 與 2542. Maximum Subsequence Score 同一 pattern，但此題是「最多 k 個」而非「恰好 k 個」，不過在降序遍歷中，每次都計算結果即可涵蓋所有情況；注意取模只在最後回傳時做