Given an integer N, representing the number of workers, an array speed[ ], where speed[i] represents the speed of the ith worker, and an array efficiency[ ], where efficiency[i] represents the efficiency of the ith 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) = 60Input: 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 pairsvoid 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 efficiencyint 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 Codeint 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 approachimport 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 pairsstatic 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 efficiencystatic 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 Codepublic 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 pairsfrom functools import cmp_to_keydef mycmp1(a, b): if(b[0] == a[0]): return b[1] - a[1] return b[0] - a[0]def mycmp2(a,b): return b-adef 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 efficiencydef 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 Inputspeed = [2, 10, 3, 1, 5, 8 ]efficiency = [5, 4, 3, 9, 7, 2 ]K = 2# Function Callprint(maximizePerformance(speed, K, efficiency)) # This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing 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 pairsfunction 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 efficiencyfunction 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 Inputvar speed = [2, 10, 3, 1, 5, 8 ];var efficiency = [5, 4, 3, 9, 7, 2 ];var K = 2;// Function Calldocument.write(maximizePerformance(speed, K, efficiency));// This code is contributed by rrrtnx.</script> |
Output:
60
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
