<p>There are <code>n</code> workers. You are given two integer arrays <code>quality</code> and <code>wage</code> where <code>quality[i]</code> is the quality of the <code>i<sup>th</sup></code> worker and <code>wage[i]</code> is the minimum wage expectation for the <code>i<sup>th</sup></code> worker.</p>

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

<ol>
	<li>Every worker in the paid group must be paid at least their minimum wage expectation.</li>
	<li>In the group, each worker&#39;s pay must be directly proportional to their quality. This means if a worker&rsquo;s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.</li>
</ol>

<p>Given the integer <code>k</code>, return <em>the least amount of money needed to form a paid group satisfying the above conditions</em>. Answers within <code>10<sup>-5</sup></code> of the actual answer will be accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == quality.length == wage.length</code></li>
	<li><code>1 &lt;= k &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= quality[i], wage[i] &lt;= 10<sup>4</sup></code></li>
</ul>

/*
So you must divide the problem into 2 parts
1. For each worker, see what other workers they are compatible with
2. Keep adding workers, until we encounter set of more than or equal to k workers compatible with each other

Observations:
For a group to be valid, all workers must be intercompatible
So, for any given worker in that group, we may be able to check if we can combine the current worker with that group?
To be compatible, there is a cost/quality ratio that must be satisfied for the worker we just have to figure out how to apply this

Suppose all workers have a cost/quality ratio:
    w[i] = cost per unit quality = cost/quality

    If a worker w[j] is compatible with w[i], then that means

        w[i] = c1 / q1
        w[j] = c2 / q2

        [Suppose q2 > q1]
        How much more should we pay w[j]?

        It should be atleast:
        expected_pay of jth worker = c1 * (q2 / q1)

        If he wants less, then we can still hire him
        If we wants more, we will not be able to combine him;

        c2 <= c1 * (q2 / q1)

        c2 * q1 <= c1 * q2
        (c2 / q2) <= (c1 / q1)
        *If we want to combine jth worker with ith worker

    Now, we encounter workers in order that they are compatible in
    Now we want to minimize the cost of hiring them
    For that, we must select the base worker as the one with min wage requirements
    Suppose we want to check cost if kth worker is chosen as base worker
        How would be calculate the best total cost?
        For that position, we would want to get (k-1) other workers and make sure cost is minimized
    Higher, the base worker ratio, the more workers we can hire.

    c1 * (q2/q1)
    c1 * (q3/q1)
    ...
    c1 * (q1/q1 + q2/q1 + q3/q1)
    We set c1 based on current worker 
    We want to track the min value of q2/q1 q3/q1 ... for all previously seen workers
    q1/q1 + q2/q1 + q3/q1 ... = (q1 + q2 + q3 + ...) / q1
    q1 is also set based on current worker
*/ 
class Solution {
public:
    using worker = tuple<double, double, double>;
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        vector<worker> workers;
        const int n = wage.size();
        for(int i=0; i<n; i++){
            double ratio = ((double)(wage[i])) / ((double)(quality[i]));
            workers.push_back({ratio, wage[i], quality[i]});
        }
        sort(workers.begin(), workers.end());
        priority_queue<double> seen;
        double q_sum{};
        double best = INT_MAX;
        for(int i=0; i<n; i++){
            // Check if we can use this as base worker
            q_sum += get<2>(workers[i]);
            seen.push(get<2>(workers[i]));
            if(seen.size() > k){
                // Remove one worker
                q_sum -= seen.top(); seen.pop();
            }
            if(seen.size() == k){
                double base_cost = get<1>(workers[i]);
                double base_quality = get<2>(workers[i]);
                double option = base_cost * (q_sum / base_quality);
                best = min(best, option);
            }
        }
        return best;
    }
};
31400