Problem statement

https://binarysearch.com/problems/Fair-Pay-Sequel/

Solution

Equal to Leetcode 0857 Minimum Cost to Hire K Workers.

Complexity

It is O(n log k) for time and O(n) for space.

Code

class Solution:
    def solve(self, quality, wage, K):
        nums = sorted((w/q, q) for q, w in zip(quality, wage))
        n, heap = len(nums), []
        for i in range(K): heappush(heap, -nums[i][1])
        sum_q, level = -sum(heap), nums[K-1][0]
        ans = sum_q * level

        if K == 0: return 0
        for i in range(K, n):
            if nums[i][1] <= - heap[0]:
                heappush(heap, -nums[i][1])
                t = heappop(heap)
                sum_q = sum_q + t + nums[i][1]
            ans = min(ans, nums[i][0] * sum_q)
            
        return ans