1383. Maximum Performance of a Team - Explanation

1. Brute Force (Recursion)

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        MOD = 1000000007
        res = 0

        def dfs(i, k, speedSum, minEff):
            nonlocal res
            res = max(res, speedSum * minEff)
            if i == n or k == 0:
                return

            dfs(i + 1, k, speedSum, minEff)
            dfs(i + 1, k - 1, speedSum + speed[i], min(minEff, efficiency[i]))

        dfs(0, k, 0, float("inf"))
        return res % MOD

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Sorting + Min-Heap

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        MOD = 10**9 + 7
        eng = sorted(zip(efficiency, speed), reverse=True)

        res = speedSum = 0
        minHeap = []

        for eff, spd in eng:
            if len(minHeap) == k:
                speedSum -= heapq.heappop(minHeap)
            speedSum += spd
            heapq.heappush(minHeap, spd)
            res = max(res, eff * speedSum)

        return res % MOD

Time & Space Complexity

Time complexity: $O(n * (\log n + \log k))$
Space complexity: $O(n + k)$

Where $n$ is the number of engineers and $k$ is the maximum number of engineers that can be selected.