程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2022-02(12)

2022-03(5)

Leetcode 1383:最大的团队表现值(超详细的解法!!!)

发布于2020-03-18 10:43     阅读(690)     评论(0)     点赞(13)     收藏(0)


公司有编号为 1nn 个工程师,给你两个数组 speedefficiency ,其中 speed[i]efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的 最大团队表现值 ,由于答案可能很大,请你返回结果对 10^9 + 7 取余后的结果。

团队表现值 的定义为:一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。

示例 1:

输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
输出:60
解释:
我们选择工程师 2(speed=10 且 efficiency=4)和工程师 5(speed=5 且 efficiency=7)。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。

示例 2:

输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
输出:68
解释:
此示例与第一个示例相同,除了 k = 3 。我们可以选择工程师 1 ,工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。

示例 3:

输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
输出:72

提示:

  • 1 <= n <= 10^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^8
  • 1 <= k <= n

解题思路

这个问题和Leetcode 857:雇佣 K 名工人的最低成本处理思路类似,此时希望efficiency要大,所以我们可以对所有的工程师按照efficiency从大到小排序。然后从前向后遍历排好序的工程师,假设此时遍历到第i个工程师(这个工程师一定是前i个中efficiency最小的),所以我们需要从前i-1个工程师里面选择k-1speed最大的工程师(可以通过小根堆维护)。

另外,还有一个问题需要考虑,因为题目条件是最多k个工程师,所以上面的思路解决了恰好k个工程师的问题,而小于k个工程师的情况也需要考虑(也就是堆中元素个数小于k-1的时候也要计算最大团队表现值)。

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        heap = []
        res = sSum = 0
        
        for e, s in sorted(zip(efficiency, speed), reverse=True):
            sSum += s
            res = max(res, sSum * e)
            heapq.heappush(heap, s)
            if len(heap) >= k: sSum -= heapq.heappop(heap)
        return res % (10**9 + 7)

这个问题的思维难度比Leetcode 857:雇佣 K 名工人的最低成本简单。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!



所属网站分类: 技术文章 > 博客

作者:战天

链接:https://www.pythonheidong.com/blog/article/265151/ac4411792fcebdfc4aef/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

13 0
收藏该文
已收藏

评论内容:(最多支持255个字符)