Untitled

/********************************************************************* JAVA *********************************************************************/
// Approach-1 (Brute Force - Heap + Math) - TLE
// T.C : O(n * (n + klogk))
// S.C : O(n+k)
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] min_wage, int k) {
        int n = quality.length;

        double result = Double.MAX_VALUE; // maximum representable finite floating-point (double) number

        for (int fixed = 0; fixed < n; fixed++) {
            double fixedRatio = (double) min_wage[fixed] / quality[fixed];

            // Create a group of workers whose wage-to-quality ratio is greater than or equal to the fixed's ratio
            double[] group = new double[n];
            int groupSize = 0;
            for (int worker = 0; worker < n; worker++) {
                double worker_wage = quality[worker] * fixedRatio;
                if (worker_wage >= min_wage[worker]) {
                    group[groupSize++] = worker_wage;
                }
            }

            if (groupSize < k)
                continue;

            PriorityQueue<Double> pq = new PriorityQueue<>(groupSize, Collections.reverseOrder());
            double sum = 0;

            // Calculate the sum of wages for the selected group of workers
            for (int i = 0; i < groupSize; i++) {
                sum += group[i];
                pq.offer(group[i]);

                if (pq.size() > k) {
                    sum -= pq.poll();
                }
            }

            result = Math.min(result, sum);
        }

        return result;
    }
}


// Approach-2 (Improved Brute Force - Heap + Math) - TLE
// T.C : O(nlogn + n * (n + klogk)) - This is worst case when no one got eliminated 
// S.C : O(n+k)
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] min_wage, int k) {
        int n = quality.length;

        double result = Double.MAX_VALUE; // maximum representable finite floating-point (double) number

        // Calculate the wage-to-quality ratio for each worker and store in a pair
        double[][] worker_ratio = new double[n][2];
        for (int worker = 0; worker < n; worker++) {
            worker_ratio[worker][0] = (double) min_wage[worker] / quality[worker];
            worker_ratio[worker][1] = quality[worker];
        }

        // Sort the workers based on their wage-to-quality ratio
        Arrays.sort(worker_ratio, (a, b) -> Double.compare(a[0], b[0]));

        for (int fixed = k - 1; fixed < n; fixed++) {
            double fixedRatio = worker_ratio[fixed][0];

            // Create a group of workers whose wage-to-quality ratio is less than or equal to the current fixed's ratio
            double[] group = new double[fixed + 1];
            for (int worker = 0; worker <= fixed; worker++) {
                double worker_wage = worker_ratio[worker][1] * fixedRatio;
                group[worker] = worker_wage;
            }

            PriorityQueue<Double> pq = new PriorityQueue<>(group.length, Collections.reverseOrder());
            double sum = 0;

            // Calculate the sum of wages for the selected group of workers
            for (double wage : group) {
                sum += wage;
                pq.offer(wage);

                if (pq.size() > k) {
                    sum -= pq.poll();
                }
            }

            result = Math.min(result, sum);
        }

        return result;
    }
}


// Approach-3 (Optimal)
// T.C : O(nlogn + klogk + n*log(k))
// S.C : O(n+k)
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] min_wage, int k) {
        int n = quality.length;

        // Calculate the wage-to-quality ratio for each worker and store in a pair
        double[][] worker_ratio = new double[n][2];
        for (int worker = 0; worker < n; worker++) {
            worker_ratio[worker][0] = (double) min_wage[worker] / quality[worker];
            worker_ratio[worker][1] = quality[worker];
        }
        // Sort the workers based on their wage-to-quality ratio
        Arrays.sort(worker_ratio, (a, b) -> Double.compare(a[0], b[0]));

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());


        // fixed size sliding window approach
        double sum_quality = 0;
        for (int i = 0; i < k; i++) {
            pq.add((int) worker_ratio[i][1]); // Push all qualities in max-heap
            sum_quality += worker_ratio[i][1]; // Find sum of qualities
        }

        double fixedRatio = worker_ratio[k - 1][0];
        double result = fixedRatio * sum_quality;

        for (int fixed = k; fixed < n; fixed++) {
            sum_quality -= pq.poll();
            sum_quality += worker_ratio[fixed][1];
            pq.add(worker_ratio[fixed][1]);
            fixedRatio = worker_ratio[fixed][0];
            result = Math.min(result, fixedRatio * sum_quality);
        }

        return result;
    }
}