857. Minimum Cost to Hire K Workers

Minimum Cost to Hire K Workers (LeetCode 857) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.

How to solve Minimum Cost to Hire K Workers

Minimum Cost to Hire K Workers is a Scheduling and Minimum Cost problem, part of Heap (Priority Queue) Patterns. Solve scheduling and optimization problems using priority queue with greedy approach.

Work towards the solution in these steps:

1. Consider how sorting the workers by a certain ratio might help in making greedy selections.
2. Think about the ratio of wage to quality for each worker and how it can determine the minimum pay scale.
3. After sorting by this ratio, explore how to select k workers with the smallest total quality to minimize cost.

The reference solution runs in O(n log n) time and O(n) space.

The Minimum Cost to Hire K Workers solution and editorial walks through the full approach with reference code.

Problem statement

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:

- Every worker in the paid group must be paid at least their minimum wage expectation.

- 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.

Constraints:

- n == quality.length == wage.length

- 1 <= k <= n <= 104

- 1 <= quality[i], wage[i] <= 104

Topics and companies

Topics: Array, Greedy, Sorting, Heap (Priority Queue).

Reported in interviews at Google.

How to practise Minimum Cost to Hire K Workers on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n) time and O(n) space.

Open Minimum Cost to Hire K Workers in the code editor, or read the Minimum Cost to Hire K Workers editorial for a worked solution with its approach and complexity analysis.

Where Minimum Cost to Hire K Workers sits in the DSA pattern sheet

• Heap (Priority Queue) Patterns pattern guide
• Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern
• The full DSA patterns sheet

Problems related to Minimum Cost to Hire K Workers

Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:

• Furthest Building You Can Reach — Medium, same subpattern
• IPO — Hard, same subpattern
• Longest Happy String — Medium, same subpattern
• Maximum Average Pass Ratio — Medium, same subpattern
• Meeting Rooms II — Medium, same subpattern
• Meeting Rooms III — Hard, same subpattern

Minimum Cost to Hire K Workers FAQ