[LeetCode] 857. Minimum Cost to Hire K Workers

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/description/

leetcode - Minimum Cost to Hire K Workers

문제 유형 : 우선순위 큐, 정렬

문제 난이도 : Hard

 

문제

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.

 

 

n명의 노동자들이 있다. 두 개의 정수배열 quality와 wage가 있다. quality[i]에는 i번째 노동자의 일 퀄리티가, wage[i]에는 최소로 받아야 하는 급여가 들어있다.

 

k명의 노동자를 고용하려고 한다.

다음의 룰을 따라야 한다:

1. 모든 노동자들의 페이는 각자 최소 wage만큼은 받아야 합니다.
2. 그룹에서, 각 노동자들의 급여는 그들의 퀄리티에 정비례해야 합니다.
   즉, 한 노동자의 2배 높은 퀄리티를 가진 노동자는 두 배는 받아야 합니다.

 

1e-5의 오차가 허용됩니다. 최소의 고용비용을 구하시오.

 

풀이

우선 가장 중요한 것은, 퀄리티 대비 돈을 얼마나 요구하는지다. 

지출해야하는 최소 급여는 (k명의 퀄리티의 합) * (그중 가장 가성비가 나쁜 사람의 요구비율)이다.

가장 요구하는 퀄리티 대비 페이가 쎈 사람을 기준으로 잡아야 룰 1을 만족할 수 있고,

퀄리티의 합에 비율을 곱한 것을 통해 2번을 만족시킨다. 모두 그 가장 높은 요구비율로 급여를 맞춰주고, 각자 퀄리티별로 급여를 비례해서 주면 위 식이 나온다.

 

우선, 2차원배열을 만들어서, {비율, 인덱스}로 저장한다.

그 뒤, 비율을 기준으로 오름차순 정렬한다.

최대 힙의 우선순위 큐도 만들고, 누적시킬 퀄리티의 합과 최대비율도 저장시킨다.

 

우선, 가장 가성비가 좋은 k명의 멤버를 선발하자.

for(int i = 0; i < k; i++)를 통해서 퀄리티의 합을 누적시키고, 비율의 최대값을 갱신시킨다.

우선순위 큐에 각 노동자의 퀄리티를 저장한다.

 

처음 만든 팀의 총액을 구해놓는다.

그 뒤, for(int i = k; i < n; i++)를 통해서 최대비율을 업데이트하고, 기존 가장 퀄리티가 높은 멤버를 쫓아낸다. 즉, 퀄리티합에서 우선순위 큐의 top만큼 빼고, pop한다. 그리고 퀄리티합을 새로 더한다. 우선순위큐에 새 멤버의 퀄리티를 저장시킨다. 

총액도 업데이트시켜준다.

 

최종적으로 계산된 총액을 반환한다.

 

인력을 정리시키는 무서운 문제..

 

코드

C++

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = wage.size();
        vector<pair<double, int>> table;
        for(int i = 0; i < n; i++) {
            table.push_back({(double)(wage[i]) / quality[i], i});
        }

        sort(table.begin(), table.end());
        priority_queue<int> pq;
        int qualitySum = 0;
        double maxRate = 0;
        for(int i = 0; i < k; i++) {
            qualitySum += quality[table[i].second];
            maxRate = max(maxRate, table[i].first);
            pq.push(quality[table[i].second]);
        }

        double ans = maxRate * qualitySum;
        for(int i = k; i < n; i++) {
            maxRate = max(maxRate, table[i].first);
            qualitySum -= pq.top(); 
            pq.pop();

            qualitySum += quality[table[i].second];
            pq.push(quality[table[i].second]);
            ans = min(ans, maxRate * qualitySum);
        }

        return ans;
    }
};