Given an array of pairs arr[], the task is to find the maximum cost choosing at most K pairs. The cost of an array of pairs is defined as product of the sum of first elements of the selected pair and the minimum among the second elements of the selected pairs. For example, if the following pairs are selected (3, 7), (9, 2) and (2, 5), then the cost will be (3+9+2)*(2) = 28.
Examples:
Input: arr[] = { {4, 7}, {15, 1}, {3, 6}, {6, 8} }, K = 3
Output: 78
The pairs 1, 3 and 4 are selected, therefore the cost = (4 + 3 + 6) * 6 = 78.Input: arr[] = { {62, 21}, {31, 16}, {19, 2}, {32, 19}, {12, 17} }, K = 4
Output: 2192
Approach: If the second element of a pair is fixed in the answer, then K-1(or less) other pairs are to be selected from those pairs whose second element is greater or equal to the fixed second element and the answer will be maximum if those are chosen such that the sum of first elements is maximum. So, sort the array according to second element and then iterate in descending order taking maximum sum of the first element of K pairs(or less). The maximum sum of first element K pairs can be taken with the help of Set data structure.
Below is the implementation of the above approach:
CPP
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Driver function to sort the array elements// by second element of pairsbool sortbysec(const pair<int, int>& a, const pair<int, int>& b){ return (a.second < b.second);}// Function that returns the maximum cost of// an array of pairs choosing at most K pairs.int maxCost(pair<int, int> a[], int N, int K){ // Initialize result and temporary sum variables int res = 0, sum = 0; // Initialize Set to store K greatest // element for maximum sum set<pair<int, int> > s; // Sort array by second element sort(a, a + N, sortbysec); // Iterate in descending order for (int i = N - 1; i >= 0; --i) { s.insert(make_pair(a[i].first, i)); sum += a[i].first; while (s.size() > K) { auto it = s.begin(); sum -= it->first; s.erase(it); } res = max(res, sum * a[i].second); } return res;}// Driver Codeint main(){ pair<int, int> arr[] = { { 12, 3 }, { 62, 21 }, { 31, 16 }, { 19, 2 }, { 32, 19 }, { 12, 17 }, { 1, 7 } }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; cout << maxCost(arr, N, K); return 0;} |
Java
// Function that returns the maximum cost of an array of pairs choosing at most K pairs.public static int maxCost(final Pair<Integer, Integer>[] a, final int N, final int K) { // Initialize result and temporary sum variables int res = 0, sum = 0; // Initialize Set to store K greatest element for maximum sum final Set<Pair<Integer, Integer>> s = new TreeSet<Pair<Integer, Integer>>( (x, y) -> Integer.compare(x.getKey(), y.getKey())); // Sort array by second element Arrays.sort(a, 0, N, Main::sortbysec); // Iterate in descending order for (int i = N - 1; i >= 0; --i) { s.add(new Pair<>(a[i].getKey(), i)); sum += a[i].getKey(); while (s.size() > K) { final Iterator<Pair<Integer, Integer>> it = s.iterator(); final Pair<Integer, Integer> p = it.next(); sum -= p.getKey(); it.remove(); } res = Math.max(res, sum * a[i].getValue()); } return res;}// Driver Codepublic static void main(final String[] args) { final Pair<Integer, Integer>[] arr = new Pair[] { new Pair<>(12, 3), new Pair<>(62, 21), new Pair<>(31, 16), new Pair<>(19, 2), new Pair<>(32, 19), new Pair<>(12, 17), new Pair<>(1, 7) }; final int N = arr.length; final int K = 3; System.out.println(maxCost(arr, N, K));} |
Python3
import heapq# Function that returns the maximum cost of an array of pairs choosing at most K pairs.def maxCost(a, N, K): # Initialize result and temporary sum variables res = 0 sum = 0 # Initialize heap to store K greatest element for maximum sum heap = [] # Sort array by second element a = sorted(a, key=lambda x: x[1]) # Iterate in descending order for i in range(N-1, -1, -1): heapq.heappush(heap, a[i][0]) sum += a[i][0] while len(heap) > K: sum -= heapq.heappop(heap) res = max(res, sum * a[i][1]) return res# Driver Codeif __name__ == "__main__": arr = [(12, 3), (62, 21), (31, 16), (19, 2), (32, 19), (12, 17), (1, 7)] N = len(arr) K = 3 print(maxCost(arr, N, K))# This code is contributed by Prince Kumar |
C#
// C# porgrm for the above approachusing System;using System.Collections.Generic;public class Pair<T1, T2> { public T1 Key; public T2 Value; public Pair(T1 key, T2 value) { Key = key; Value = value; }}public class Program { // Custom comparator to sort pairs by first element in descending order public static int SortByFirstDesc(Pair<int, int> a, Pair<int, int> b) { return b.Key.CompareTo(a.Key); } // Function that returns the maximum cost of an array of pairs choosing at most K pairs. public static int MaxCost(Pair<int, int>[] a, int N, int K) { // Initialize result and temporary sum variables int res = 0, sum = 0; // Initialize Set to store K greatest element for maximum sum SortedSet<Pair<int, int>> s = new SortedSet<Pair<int, int>>( Comparer<Pair<int, int>>.Create(SortByFirstDesc)); // Sort array by first element in descending order Array.Sort(a, 0, N, Comparer<Pair<int, int>>.Create(SortByFirstDesc)); // Iterate in descending order for (int i = 0; i < N; ++i) { s.Add(new Pair<int, int>(a[i].Key, i)); sum += a[i].Key; while (s.Count > K) { Pair<int, int> p = s.Min; sum -= p.Key; s.Remove(p); } res = Math.Max(res, sum * a[i].Value); } return res; } // Driver Code public static void Main() { Pair<int, int>[] arr = new Pair<int, int>[] { new Pair<int, int>(12, 3), new Pair<int, int>(62, 21), new Pair<int, int>(31, 16), new Pair<int, int>(19, 2), new Pair<int, int>(32, 19), new Pair<int, int>(12, 17), new Pair<int, int>(1, 7) }; int N = arr.Length; int K = 3; Console.WriteLine(MaxCost(arr, N, K)); }}// This code is contributed by adityasharmadev01 |
Javascript
// Javascript program for the above approach// Function to sort the array elements by second element of pairsfunction sortbysec(a, b) { return a[1] - b[1];}// Function that returns the maximum cost of// an array of pairs choosing at most K pairs.function maxCost(a, N, K) { // Initialize result and temporary sum variables let res = 0; let sum = 0; // Initialize array to store K greatest element for maximum sum let arr = []; // Sort array by second element a.sort(sortbysec); // Iterate in descending order for (let i = N - 1; i >= 0; --i) { arr.push([a[i][0], i]); sum += a[i][0]; while (arr.length > K) { let min = Infinity; let idx = -1; for (let j = 0; j < arr.length; j++) { if (arr[j][0] < min) { min = arr[j][0]; idx = j; } } sum -= arr[idx][0]; arr.splice(idx, 1); } res = Math.max(res, sum * a[i][1]); } return res;}// Driver Codeconst arr = [ [12, 3], [62, 21], [31, 16], [19, 2], [32, 19], [12, 17], [1, 7],];const N = arr.length;const K = 3;console.log(maxCost(arr, N, K)); // This code is contributed by princekumaras |
Output:
2000
Time Complexity: O(N*logN)
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!