LC-1383 Hard LeetCode

1383. Maximum Performance of a Team

Array Greedy Sorting Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 48% Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Reading material

Arrays & Hashing 12 min Greedy 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

import itertools
import heapq


class Solution(object):
    def maxPerformance(self, n, speed, efficiency, k):
        """
        :type n: int
        :type speed: List[int]
        :type efficiency: List[int]
        :type k: int
        :rtype: int
        """
        MOD = 10**9 + 7
        result, s_sum = 0, 0
        min_heap = []
        for e, s in sorted(itertools.izip(efficiency, speed), reverse=True):
            s_sum += s
            heapq.heappush(min_heap, s)
            if len(min_heap) > k:
                s_sum -= heapq.heappop(min_heap)
            result = max(result, s_sum*e)
        return result % MOD

Solution from kamyu104/LeetCode-Solutions · MIT