Minimum Cost to Hire K Workers
Hard · Heap & Priority Queue · about 35 minutes
Asked at Google, Amazon, Meta, Microsoft.
Worker i has quality[i] and minimum wage expectation wage[i]. Hire exactly k workers so that each is paid in proportion to their quality (relative to the others in the group) and at least their minimum wage. Return the least total cost; answers within 10⁻⁵ are accepted.