Maximum cost of a value over the range [1, N] such that values lies in at most K given ranges
Given a positive integer N and an array arr[] of size M of the type {L, R, C} such that C is the cost of choosing an element in the range [L, R] and a positive integer K, the task is to find the maximum cost of a value over the range [1, N] such that values lies in at most K given range arr[].
Examples:
Input: arr[] = {{2, 8, 800}, {6, 9, 1500}, {4, 7, 200}, {3, 5, 400}}, K = 2
Output: 2300
Explanation:
The item chosen is 6 and the costs chosen are 0th and 1st indices such that the 6 belongs into the range of 2 to 8 and 6 to 9. Therefore the total sum of the costs 800 + 1500 is 2300, which is maximum.Input: arr[] = {{1, 3, 400}, {5, 5, 500}, {2, 3, 300}}, K = 3
Output: 700
Approach: The given problem can be solved by storing all the costs for every item i which lies in the interval range L to R, and sorting the chosen costs in non-increasing order. Then comparing the sum of the first K costs of all items. Below steps can be followed:
- Initialize a variable, say totMaxSum = 0 to store the maximum sum of the cost.
- Initialize a variable, say sum = 0 to store the ith item sum of the cost.
- Initialize a vector, say currCost to store the costs for the ith item.
- Iterate over the range of [1, N] using the variable i and nested iterate over the range of [0, M – 1] using the variable j and perform the following steps:
- If the value of i lies over the range [arr[i][0], arr[i][1]], then add the value of arr[i][2] to the vector currCost.
- Sort the vector currCost in non-increasing order.
- Iterate over the vector currCost and add the values of the first K elements to sum.
- Update the value of totMaxSum by max(totMaxSum, sum).
- After completing the above steps, print the value of totMaxSum as the maximum sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to maximize the total cost // by choosing an item which lies in // the interval L to R void maxTotalCost(vector<vector< int > >& arr, int M, int N, int K) { // Stores the total maximum sum int totMaxSum = 0; for ( int i = 1; i <= N; ++i) { // Stores the cost for ith item vector< int > currCost; for ( int j = 0; j < M; ++j) { // Check if the ith item // belongs in the interval if (arr[j][0] <= i && arr[j][1] >= i) { // Add the jth cost currCost.push_back(arr[j][2]); } } // Sort the currCost[] in the // non increasing order sort(currCost.begin(), currCost.end(), greater< int >()); // Stores the ith item sum int sum = 0; // Choose at most K costs for ( int j = 0; j < K && j < currCost.size(); ++j) { // Update the sum sum += currCost[j]; } // Update the totMaxSum totMaxSum = max(totMaxSum, sum); } // Print the value of totMaxSum cout << totMaxSum << endl; } // Driver Code int main() { int N = 10; vector<vector< int > > arr = { { 2, 8, 800 }, { 6, 9, 1500 }, { 4, 7, 200 }, { 3, 5, 400 } }; int M = arr.size(); int K = 2; maxTotalCost(arr, M, N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to maximize the total cost // by choosing an item which lies in // the interval L to R static void maxTotalCost( int [][] arr, int M, int N, int K) { // Stores the total maximum sum int totMaxSum = 0 ; for ( int i = 1 ; i <= N; ++i) { // Stores the cost for ith item Vector<Integer> currCost = new Vector<Integer>(); for ( int j = 0 ; j < M; ++j) { // Check if the ith item // belongs in the interval if (arr[j][ 0 ] <= i && arr[j][ 1 ] >= i) { // Add the jth cost currCost.add(arr[j][ 2 ]); } } // Sort the currCost[] in the // non increasing order Collections.sort(currCost,Collections.reverseOrder()); // Stores the ith item sum int sum = 0 ; // Choose at most K costs for ( int j = 0 ; j < K && j < currCost.size(); ++j) { // Update the sum sum += currCost.get(j); } // Update the totMaxSum totMaxSum = Math.max(totMaxSum, sum); } // Print the value of totMaxSum System.out.print(totMaxSum + "\n" ); } // Driver Code public static void main(String[] args) { int N = 10 ; int [][] arr = { { 2 , 8 , 800 }, { 6 , 9 , 1500 }, { 4 , 7 , 200 }, { 3 , 5 , 400 } }; int M = arr.length; int K = 2 ; maxTotalCost(arr, M, N, K); } } // This code is contributed by shikhasingrajput |
Python3
# python program for the above approach # Function to maximize the total cost # by choosing an item which lies in # the interval L to R def maxTotalCost(arr, M, N, K): # Stores the total maximum sum totMaxSum = 0 for i in range ( 1 , N + 1 ): # Stores the cost for ith item currCost = [] for j in range ( 0 , M): # Check if the ith item # belongs in the interval if (arr[j][ 0 ] < = i and arr[j][ 1 ] > = i): # Add the jth cost currCost.append(arr[j][ 2 ]) # Sort the currCost[] in the # non increasing order currCost.sort() # Stores the ith item sum sum = 0 # Choose at most K costs for j in range ( 0 , K): # Update the sum if j > = len (currCost): break sum + = currCost[j] # Update the totMaxSum totMaxSum = max (totMaxSum, sum ) # Print the value of totMaxSum print (totMaxSum) # Driver Code if __name__ = = "__main__" : N = 10 arr = [[ 2 , 8 , 800 ], [ 6 , 9 , 1500 ], [ 4 , 7 , 200 ], [ 3 , 5 , 400 ] ] M = len (arr) K = 2 maxTotalCost(arr, M, N, K) # This code is contributed by rakeshsahni |
C#
// C++ program for the above approach using System; using System.Collections.Generic; class GFG { // Function to maximize the total cost // by choosing an item which lies in // the interval L to R static void maxTotalCost( int [, ] arr, int M, int N, int K) { // Stores the total maximum sum int totMaxSum = 0; for ( int i = 1; i <= N; ++i) { // Stores the cost for ith item List< int > currCost = new List< int >(); for ( int j = 0; j < M; ++j) { // Check if the ith item // belongs in the interval if (arr[j, 0] <= i && arr[j, 1] >= i) { // Add the jth cost currCost.Add(arr[j, 2]); } } // Sort the currCost[] in the // non increasing order currCost.Sort(); // Stores the ith item sum int sum = 0; // Choose at most K costs for ( int j = 0; j < K && j < currCost.Count; ++j) { // Update the sum sum += currCost[j]; } // Update the totMaxSum totMaxSum = Math.Max(totMaxSum, sum); } // Print the value of totMaxSum Console.WriteLine(totMaxSum); } // Driver Code public static void Main() { int N = 10; int [, ] arr = { { 2, 8, 800 }, { 6, 9, 1500 }, { 4, 7, 200 }, { 3, 5, 400 } }; int M = arr.GetLength(0); int K = 2; maxTotalCost(arr, M, N, K); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to maximize the total cost // by choosing an item which lies in // the interval L to R function maxTotalCost(arr, M, N, K) { // Stores the total maximum sum let totMaxSum = 0; for (let i = 1; i <= N; ++i) { // Stores the cost for ith item let currCost = []; for (let j = 0; j < M; ++j) { // Check if the ith item // belongs in the interval if (arr[j][0] <= i && arr[j][1] >= i) { // Add the jth cost currCost.push(arr[j][2]); } } // Sort the currCost[] in the // non increasing order currCost.sort( function (a, b) { return b - a }) // Stores the ith item sum let sum = 0; // Choose at most K costs for (let j = 0; j < K && j < currCost.length; ++j) { // Update the sum sum += currCost[j]; } // Update the totMaxSum totMaxSum = Math.max(totMaxSum, sum); } // Print the value of totMaxSum document.write(totMaxSum + '<br>' ); } // Driver Code let N = 10; let arr = [[2, 8, 800], [6, 9, 1500], [4, 7, 200], [3, 5, 400]]; let M = arr.length; let K = 2; maxTotalCost(arr, M, N, K); // This code is contributed by Potta Lokesh </script> |
2300
Time Complexity: O(N*M*log M)
Auxiliary Space: O(N*M)