Maximize product of sum of speeds of K workers and their minimum efficiency

0 0 7 minutes read

Given an integer N, representing the number of workers, an array speed[ ], where speed[i] represents the speed of the i^th worker, and an array efficiency[ ], where efficiency[i] represents the efficiency of the i^th worker, and an integer K, the task is to select K workers such that the ( Sum of speeds of all the workers ) * ( Minimum efficiency of among K workers ) is maximum possible.

Examples:

Input: N = 6, speed[] = {2, 10, 3, 1, 5, 8}, efficiency[] = {5, 4, 3, 9, 7, 2}, K = 2
Output: 60
Explanation:
Selecting 2nd worker (Speed = 10 and Efficiency = 4) and 5th worker ( Speed = 5 and Efficiency = 7).
Therefore, the maximum sum possible = (10 + 5) * min(4, 7) = 60

Input: N = 6, speed[] = {2, 10, 3, 1, 5, 8}, efficiency[] = {5, 4, 3, 9, 7, 2}, K = 3
Output: 68

Approach: Follow the steps below to solve the problem:

Initialize a vector of pairs arr[ ] where arr[i] equals {efficiency[i], speed[i]} of size N.
Sort the arr[ ] in decreasing order of efficiency.
Initialize a min priority_queue that stores the speed of workers.
Initialize variables say, SumOfSpeed = 0 and Ans = 0.
Iterate over arr[ ] and do the following:
- Add arr[i].first to the SumOfSpeed
- Push speed[i] in priority_queue.
- If size of the priority_queue exceeds K, the pop the front of the priority_queue and subtract from SumOfSpeed.
- Update Ans as max of Ans and SumOfSpeed * efficiency[i].
Finally, return the Ans.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate array of pairs
void generateArrayofPairs(int n, vector<int>& speed,
                          vector<int>& efficiency,
                          vector<pair<int, int> >& arr)
{
 
    for (int i = 0; i < n; i++) {
 
        arr[i] = { efficiency[i], speed[i] };
    }
 
    sort(arr.rbegin(), arr.rend());
}
 
// Function to find the maximum
// product of worker speeds and
// their minimum efficiency
int maximizePerformance(vector<int>& speed, int K,
                        vector<int>& efficiency)
{
 
    int n = speed.size();
    vector<pair<int, int> > arr(n);
 
    // Function to generate
    // sorted array of pairs
    generateArrayofPairs(n, speed,
                         efficiency, arr);
 
    // Initialize priority queue
    priority_queue<int, vector<int>,
                   greater<int> >
        pq;
 
    // Initialize ans and sumofspeed
    int ans = 0;
    int SumOfSpeed = 0;
 
    // Traversing the arr of pairs
    for (auto& it : arr) {
 
        int e = it.first;
        int s = it.second;
 
        // Updating sum of speed
        SumOfSpeed += s;
 
        // Pushing in priority queue
        pq.push(s);
 
        // If team consists of more than
        // K workers
        if (pq.size() > K) {
 
            int temp = pq.top();
            SumOfSpeed -= temp;
            pq.pop();
        }
 
        // Taking the maximum performance
        // that can be formed
        ans = max(ans, SumOfSpeed * e);
    }
 
    // Finally return the ans
    return ans;
}
 
// Driver Code
int main()
{
    // Given Input
    vector<int> speed = { 2, 10, 3, 1, 5, 8 };
    vector<int> efficiency = { 5, 4, 3, 9, 7, 2 };
    int K = 2;
 
    // Function Call
    cout << maximizePerformance(
        speed, K, efficiency);
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
static class pair
{
    int first, second;
      
    public pair(int first, int second) 
    {
        this.first = first;
        this.second = second;
    }   
}
 
// Function to generate array of pairs
static void generateArrayofPairs(int n, Vector<Integer> speed,
                          Vector<Integer> efficiency,
                          Vector<pair > arr)
{
 
    for (int i = 0; i < n; i++) {
 
        arr.insertElementAt(new pair(efficiency.elementAt(i), speed.elementAt(i)), i);
    }
 
    Collections.sort(arr, new Comparator<pair>() {
            @Override public int compare(pair p1, pair p2)
            {
                  if (p1.first != p2.first)
                    return (p2.first - p1.first);
                  return p2.second - p1.second;
            }
        });
}
 
// Function to find the maximum
// product of worker speeds and
// their minimum efficiency
static int maximizePerformance(Vector<Integer> speed, int K,
                        Vector<Integer> efficiency)
{
 
    int n = speed.size();
    Vector<pair > arr = new Vector<>();
 
    // Function to generate
    // sorted array of pairs
    generateArrayofPairs(n, speed,
                         efficiency, arr);
 
    // Initialize priority queue
      PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
 
    // Initialize ans and sumofspeed
    int ans = 0;
    int SumOfSpeed = 0;
 
    // Traversing the arr of pairs
    for (int i = 0; i < arr.size(); i++) {
 
        int e = arr.elementAt(i).first;
        int s = arr.elementAt(i).second;
 
        // Updating sum of speed
        SumOfSpeed += s;
 
        // Pushing in priority queue
        pq.add(s);
 
        // If team consists of more than
        // K workers
        if (pq.size() > K) {
 
            int temp = pq.peek();
            SumOfSpeed -= temp;
            pq.poll();
        }
 
        // Taking the maximum performance
        // that can be formed
        ans = Math.max(ans, SumOfSpeed * e);
    }
 
    // Finally return the ans
    return ans;
}
 
// Driver Code
public static void main (String[] args) {
     
      // Given Input
    Vector<Integer> speed = new Vector<Integer>();
    speed.add(2);
      speed.add(10); 
      speed.add(3); 
      speed.add(1);
      speed.add(5); 
      speed.add(8);
   
    Vector<Integer> efficiency = new Vector<Integer>();
      efficiency.add(5);
      efficiency.add(4); 
      efficiency.add(3); 
      efficiency.add(9);
      efficiency.add(7);
      efficiency.add(2);
   
      int K = 2;
 
    // Function Call
    System.out.println(maximizePerformance(
        speed, K, efficiency));
}
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python program for the above approach
 
# Function to generate array of pairs
from functools import cmp_to_key
 
def mycmp1(a, b):
    if(b[0] == a[0]):
        return b[1] - a[1]
    return b[0] - a[0]
 
def mycmp2(a,b):
    return b-a
 
def generateArrayofPairs(n, speed, efficiency, arr):
 
    for i in range(n):
        arr[i] = [ efficiency[i], speed[i] ]
 
    arr.sort(key =cmp_to_key(mycmp1))
 
    return arr
 
# Function to find the maximum
# product of worker speeds and
# their minimum efficiency
def maximizePerformance(speed, K, efficiency):
 
    n = len(speed)
    arr = [[0 for j in range(2)]for i in range(n)]
 
    # Function to generate
    # sorted array of pairs
    arr = generateArrayofPairs(n, speed,efficiency, arr)
 
    # Initialize priority queue
    pq = []
 
    # Initialize ans and sumofspeed
    ans = 0
    SumOfSpeed = 0
 
    # Traversing the arr of pairs
    for it in arr:
 
        e = it[0]
        s = it[1]
 
        # Updating sum of speed
        SumOfSpeed += s
 
        # Pushing in priority queue
        pq.append(s)
 
        pq.sort(key = cmp_to_key(mycmp2))
 
        # If team consists of more than
        # K workers
        if (len(pq) > K):
 
            temp = pq[len(pq)-1]
            SumOfSpeed -= temp
            pq.pop()
         
        # Taking the maximum performance
        # that can be formed
        ans = max(ans, SumOfSpeed * e)
 
    # Finally return the ans
    return ans
 
# Driver Code
# Given Input
speed = [2, 10, 3, 1, 5, 8 ]
efficiency = [5, 4, 3, 9, 7, 2 ]
K = 2
 
# Function Call
print(maximizePerformance(speed, K, efficiency))
   
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
class GFG
{
    public class Pair
    {
        public int first, second;
 
        public Pair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
    }
 
    // Function to generate array of pairs
    static void generateArrayofPairs(int n, List<int> speed,
                    List<int> efficiency,
                    List<Pair> arr)
    {
 
        for (int i = 0; i < n; i++)
        {
 
            arr.Insert(i, new Pair(efficiency[i], speed[i]));
        }
 
        arr.Sort((pair1, pair2) =>
        {
            if (pair1.first != pair2.first)
                return pair2.first - pair1.first;
            return pair2.second - pair1.second;
        });
    }
 
    // Function to find the maximum
    // product of worker speeds and
    // their minimum efficiency
    static int maximizePerformance(List<int> speed, int K,
                    List<int> efficiency)
    {
 
        int n = speed.Count;
        List<Pair> arr = new List<Pair>();
 
        // Function to generate
        // sorted array of pairs
        generateArrayofPairs(n, speed,
                        efficiency, arr);
 
        // Initialize priority queue
        SortedSet<int> pq = new SortedSet<int>();
 
        // Initialize ans and sumofspeed
        int ans = 0;
        int SumOfSpeed = 0;
 
        // Traversing the arr of pairs
        for (int i = 0; i < arr.Count; i++)
        {
 
            int e = arr[i].first;
            int s = arr[i].second;
 
            // Updating sum of speed
            SumOfSpeed += s;
 
            // Pushing in priority queue
            pq.Add(s);
 
            // If team consists of more than
            // K workers
            if (pq.Count > K)
            {
 
                int temp = pq.Min;
                SumOfSpeed -= temp;
                pq.Remove(temp);
            }
 
            // Taking the maximum performance
            // that can be formed
            ans = Math.Max(ans, SumOfSpeed * e);
        }
 
        // Finally return the ans
        return ans;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
 
 
        // Given Input
        List<int> speed = new List<int>() { 2, 10, 3, 1, 5, 8 };
 
        List<int> efficiency = new List<int>() { 5, 4, 3, 9, 7, 2 };
 
        int K = 2;
 
        // Function Call
        Console.WriteLine(maximizePerformance(speed, K, efficiency));
    }
}

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to generate array of pairs
function generateArrayofPairs(n, speed, efficiency, arr)
{
 
    for (var i = 0; i < n; i++) {
 
        arr[i] = [ efficiency[i], speed[i] ];
    }
 
    arr.sort((a,b)=>{
        if(b[0] == a[0])
            return b[1] - a[1]
        return b[0] - a[0];
    });
 
    return arr;
}
 
// Function to find the maximum
// product of worker speeds and
// their minimum efficiency
function maximizePerformance(speed, K, efficiency)
{
 
    var n = speed.length;
    var arr = Array.from(Array(n),()=>new Array(2).fill(0));
 
    // Function to generate
    // sorted array of pairs
    arr = generateArrayofPairs(n, speed,
                         efficiency, arr);
 
    // Initialize priority queue
    var pq = [];
 
    // Initialize ans and sumofspeed
    var ans = 0;
    var SumOfSpeed = 0;
 
    // Traversing the arr of pairs
    for (var it of arr) {
 
        var e = it[0];
        var s = it[1];
 
        // Updating sum of speed
        SumOfSpeed += s;
 
        // Pushing in priority queue
        pq.push(s);
 
        pq.sort((a,b)=>b-a);
 
        // If team consists of more than
        // K workers
        if (pq.length > K) {
 
            var temp = pq[pq.length-1];
            SumOfSpeed -= temp;
            pq.pop();
        }
         
 
        // Taking the maximum performance
        // that can be formed
        ans = Math.max(ans, SumOfSpeed * e);
    }
 
    // Finally return the ans
    return ans;
}
 
// Driver Code
// Given Input
var speed = [2, 10, 3, 1, 5, 8 ];
var efficiency = [5, 4, 3, 9, 7, 2 ];
var K = 2;
 
// Function Call
document.write(maximizePerformance(speed, K, efficiency));
 
// This code is contributed by rrrtnx.
</script>

Output:

Time Complexity: O(NLogN)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!