[LeetCode 857] Minimum Cost to Hire K Workers

Problem Link

There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.

We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:

1. Every worker in the paid group must be paid at least their minimum wage expectation.
2. In the group, each worker's pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.

Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output: 30.66667
Explanation: We pay 4 to 0th worker, 13.33333 to 2nd and 3rd workers separately.

Solution

• 문제의 핵심은 두 가지 조건에 있다.

  1. 그룹 내 사람들 각각의 minimum wage[i]는 넘겨주어야 한다.
  2. 만약 quality가 어떤 사람의 2배인 사람이 있다면, 더 낮은 quality의 사람보다 2배의 wage를 받아야 하는 것이 당연하다.

• 이러한 조건으로 최소한의 비용을 지불하여 group을 짜고 싶은 내용의 문제다.

  • 회사 마인드로 접근해야 한달까..

• 우선 각 사람의 wage/quality를 구하여 이를 오름차순 정렬한다.

  • 말그대로 quality는 좋은데 wage가 낮은 사람이 회사 입장에서는 제일 고용하고 싶은 사람일테니..

    • 앞에서부터 우선 순위로 뽑고 싶은 k명을 먼저 고용한다.

• 이 때, qual_sum과 max_rate의 값이 매우 중요한 역할을 한다.

  • Example 1을 예를 들면, 10의 quality를 가진 사람과 5의 quality를 가진 사람이 wage가 각각 70, 30이다.

    • wage/quality 비율은 10인 사람이 7, 5인 사람이 6이다.
    • 10의 사람은 5인 사람의 2배 wage를 받아야 하기 때문에, 최소가 30인 5의 사람은 35의 wage를 받고 고용된다.

  • 다시 말해, wage/quality 비율을 동일하게 만족시킬 수 있도록 max_rate를 찾아주어야 한다.

    • 그리고 10과 5를 모두 합한 qual_sum과 곱하여 $7(max(6, 7))*15(10+5)$를 cost로 계산할 수 있게 만들어주는 것이다.

• 이제 wage/quality가 낮은 순으로 k명을 뽑아 놓고 봤더니, 뒤에 있는 사람들을 고용할 때 cost가 더 작았던 경우까지 생각해준다.

  • 이럴 때 필요한 게 max heap으로 저장한 k명 내의 quality 값이다.

    • 현재 quality로 cost를 계산한 값이 k명 내의 quality 중 큰 값을 뽑아 기존 qual_sum에 +(-quality)한 값으로 * max_rate한 값보다 작다면 업데이트한다.

소스 코드

from heapq import heappush, heappop, heapify

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        ratio = sorted([(w/q, q) for w, q in zip(wage, quality)])  # ratio, quality
        
        q = []
        qual_sum = 0  # initial cheap quality sum
        max_rate = 0  # initial max rate in k
        
        for i in range(k):
            rate, qual = ratio[i]
            max_rate = max(max_rate, rate)  # max ratio
            qual_sum += qual  # quality sum
            heappush(q, (-qual))  # max heap
        
        cost = qual_sum * max_rate

        for i in range(k, len(quality)):
            rate, qual = ratio[i]
            max_rate = max(max_rate, rate)
            qual_sum += heappop(q) + qual  # k내의 큰 quality 빼고 현재 quality 추가
            heappush(q, (-qual))
            cost = min(cost, qual_sum * max_rate)

        return cost

• 다른 사람의 풀이는 아래와 같다.

  • k명을 미리 뽑고, 그 이후로 또 뽑는 것이 아닌 전체 loop를 돌아 해결한다.

    • k명이 뽑힌 시점부터 매번 heap에서 가장 큰 값을 꺼내며 cost 비교를 반복한다.

소스 코드

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        ratio = sorted([(w/q, q) for w, q in zip(wage, quality)])  # ratio, quality
        answer = 1e9

        qual_sum = 0
        q = []
        for rate, qual in ratio:
            qual_sum += qual
            heappush(q, -qual)

            if len(q) > k:
                qual_sum += heappop(q)
            if len(q) == k:
                answer = min(answer, qual_sum * rate)

        return answer