Minimum Cost to Hire K Workers LeetCode solution in Python

1
class Solution:
2
    def mincostToHireWorkers(
3
        self, quality: List[int], wage: List[int], k: int
4
    ) -> float:
5
        n = len(wage)
6
        arr = [[wage[i] / quality[i], quality[i]] for i in range(n)]
7
        arr.sort(key=lambda x: x[0])
8
        kSmallest = 0
9
        pq = []
10
        for i in range(k):
11
            heapq.heappush(pq, -arr[i][1])
12
            kSmallest += arr[i][1]
13
        minCost = arr[k - 1][0] * kSmallest
14
        for c in range(k, n):
15
            if pq and abs(pq[0]) > arr[c][1]:
16
                qRem = -heappop(pq)
17
                kSmallest -= qRem
18
                kSmallest += arr[c][1]
19
                heappush(pq, -arr[c][1])
20
            minCost = min(minCost, arr[c][0] * kSmallest)
21
        return minCost