刷无穷 1383 ～ 团队表现最大化

基本信息

• 题号：1383
• 题厂：脸书
• 难度系数：难

一个团队有 n 个码工，每个码工有对应的效率和速度。问从中选「最多」k 个码工，怎么实现工作表现最大化？？？！！！

例如 n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2，返回 60. 
选择码工 （10，4）和（5，7）可达效率最高，performance = (10 + 5) * min(4, 7) = 60

解题思路

• 遇上此题就不要死磕「效率」「速度」「表现」三者之间的关系到底是怎么回事了，想办法让 performance 达到最大值就好
• 根据数学计算公式，就是如何让「速度和」和「最小效率」取到最大值。于是「贪心算法」登场了。
• 答案得知，最小效率值为 4，意味着如果码工的效率大于 4 是不可能参加计数的，于是想到用 maxHeap；
• 至于累积速度，只能在效率大于或等于 4 的码工当中选择。如果最多要选 k 个码工，那可以准备一个长度为 k 的 minHeap，累积速度 minHeap 存放 top k 速度……

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        # 初始化 maxHeap，配对为「-efficiency ～ speed」
        maxHeap = []
        heapq.heapify(maxHeap)
        for i in range(n):
            maxHeap.append([-efficiency[i], speed[i]])
            
        # 初始化存放 top k 速度的 minHeap    
        availableSpeed = []
        heapq.heapify(availableSpeed)
        
        accSpeed = 0
        res = 0
        
        # 遍历已配对的 maxHeap
        # availableSpeed 长度小于 k 时，直接往里面添加速度
        # availableSpeed 长度大于等于 k 时，看是否需要让最小值和当前速度替换
        while maxHeap:
            eff, speed = heapq.heappop(maxHeap)
            
            if len(availableSpeed) < k:
                accSpeed += speed
                heapq.heappush(availableSpeed, speed)               
            elif availableSpeed[0] < speed:
                accSpeed -= heapq.heappop(availableSpeed)
                accSpeed += speed
                
                heapq.heappush(availableSpeed, speed)
            
            res = max(res, -eff * accSpeed)
        
        return res % (10**9+7)

Constraints

• 1 <= k <= n <= 105
• speed.length == n
• efficiency.length == n
• 1 <= speed[i] <= 105
• 1 <= efficiency[i] <= 108

Big O

• Time：O（ nlogn ），遍历了长度为 n 的 maxHeap，遍历过程中用到了 heappop 和 heappush，复杂度为 logn
• Space：O（n + k），创建了长度为 n 的maxHeap 和长度为 k 的 availableSpeed

测试

• 当 k = 1 时；
• ……

总结

• 绕来绕去想了 2 天才想出来😭
• 突破口为思考用「贪心」思路获得最大值，再根据贪心思路初始化相应 maxHeap 和 minHeap 帮忙解题
• 鉴于贪心和 heap 都属于中难档算法 + 数据结构，然后还要二者结合，此题非难挡莫属😭
• 考场上遇到，赶脚很难在 30 分钟内有思路😭