Maximizing Business Profit with Non-Overlapping Ranges
Given an integer N representing the total number of products and queries[][] of size M. For each index i, queries[i] = [start, end, profit] which represents the profit the businessman will get by selling the products within the range [start, end], the task is to maximize the profit of the businessman such that each product can be sold at max once, that is there should be no overlapping of ranges.
Examples:
Input: N = 5, M = 4, queries[][] = { {1, 4, 5}, {0, 2, 3}, {3, 4, 5}, {0, 3, 6}}
Output: 8
Explanation: There are 5 products. To maximize the profit, it is better to go with {0, 2, 3} and {3, 4, 5}. Therefore, the maximum profit will be 3 + 5 = 8Input: N= 7, M = 4, queries[][] = { {1, 3, 50}, {2, 4, 10}, {3, 5, 40}, {4, 6, 70} }
Output: 120
Explanation: There are total 7 products. To maximize the profit, it is better to go with {1, 3, 50} and {4, 6, 70}. Therefore, the maximum profit will be 50 + 70 = 120
Approach: This can be solved with the following approach:
Sort the queries in increasing order of the starting point of ranges and maintain a dp[] array such that dp[i] = maximum profit which can be achieved using queries[i…M]. We can use binary search to get the next starting product which the businessman can sell.
Steps to solve the problem:
- Create a dp[] array to store the answers calculated and prevent unnecessary recursive calls.
- Create a function maximumProfit(idx, queries[][], dp), to get the maximum profit which can be achieved using queries[idx…M]. Inside the function,
- Check if index has reached the end of queries, then simply return 0.
- Check the dp[] array to see if we have previously calculated the answer for index idx, if yes then simply return dp[idx]
- At any index idx, the businessman has 2 choices,
- Do not take the current query present at index idx into our final answer.
- Take the query present at idx, that is sell the products in the range [queries[idx][0], queries[idx][1]] to get the profit queries[idx][2] and then again start selling the products after queries[idx][1]. We can find the next product which the businessman can sell using binary search to decrease our search time.
- Return the maximum of the above 2 choices.
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Finding the maximum profit by businessman int maximumProfit( int idx, vector<vector< int > >& queries, vector< int >& dp) { if (idx == queries.size()) return 0; if (dp[idx] != -1) return dp[idx]; int notTake = maximumProfit(idx + 1, queries, dp); int low = idx + 1, high = queries.size() - 1; int next_idx = queries.size(); // Finding the idx for the next offer // if we take idx as the current offer while (low <= high) { int mid = (low + high) / 2; if (queries[mid][0] > queries[idx][1]) { high = mid - 1; next_idx = mid; } else { low = mid + 1; } } // Peforming this & use binary search // to find the next idx to perform int take = queries[idx][2] + maximumProfit(next_idx, queries, dp); return dp[idx] = max(take, notTake); } // Function to initiate maximum profit function int maximizeTheProfit( int n, vector<vector< int > >& queries) { int m = queries.size(); sort(queries.begin(), queries.end()); vector< int > dp(m, -1); return maximumProfit(0, queries, dp); } // Driver code int main() { int N = 5; vector<vector< int > > queries = { { 1, 4, 5 }, { 0, 2, 3 }, { 3, 4, 5 }, { 0, 3, 6 } }; // Function call cout << maximizeTheProfit(N, queries) << endl; return 0; } |
Java
import java.util.*; public class Main { // Finding the maximum profit by businessman static int maximumProfit( int idx, List< int []> queries, int [] dp) { if (idx == queries.size()) return 0 ; if (dp[idx] != - 1 ) return dp[idx]; int notTake = maximumProfit(idx + 1 , queries, dp); int low = idx + 1 , high = queries.size() - 1 ; int next_idx = queries.size(); // Finding the idx for the next offer // if we take idx as the current offer while (low <= high) { int mid = (low + high) / 2 ; if (queries.get(mid)[ 0 ] > queries.get(idx)[ 1 ]) { high = mid - 1 ; next_idx = mid; } else { low = mid + 1 ; } } // Performing this & use binary search // to find the next idx to perform int take = queries.get(idx)[ 2 ] + maximumProfit(next_idx, queries, dp); return dp[idx] = Math.max(take, notTake); } // Function to initiate maximum profit function static int maximizeTheProfit( int n, List< int []> queries) { int m = queries.size(); queries.sort((a, b) -> Integer.compare(a[ 0 ], b[ 0 ])); int [] dp = new int [m]; Arrays.fill(dp, - 1 ); return maximumProfit( 0 , queries, dp); } // Driver code public static void main(String[] args) { int N = 5 ; List< int []> queries = new ArrayList<>(); queries.add( new int [] { 1 , 4 , 5 }); queries.add( new int [] { 0 , 2 , 3 }); queries.add( new int [] { 3 , 4 , 5 }); queries.add( new int [] { 0 , 3 , 6 }); // Function call System.out.println(maximizeTheProfit(N, queries)); } } |
Python3
# Function to find the maximum profit def maximumProfit(idx, queries, dp): if idx = = len (queries): return 0 if dp[idx] ! = - 1 : return dp[idx] notTake = maximumProfit(idx + 1 , queries, dp) low, high = idx + 1 , len (queries) - 1 next_idx = len (queries) # Finding the idx for the next offer # if we take idx as the current offer while low < = high: mid = (low + high) / / 2 if queries[mid][ 0 ] > queries[idx][ 1 ]: high = mid - 1 next_idx = mid else : low = mid + 1 # Peforming this & use binary search # to find the next idx to perform take = queries[idx][ 2 ] + maximumProfit(next_idx, queries, dp) dp[idx] = max (take, notTake) return dp[idx] # Function to initiate maximum profit function def maximizeTheProfit(n, queries): m = len (queries) queries.sort() dp = [ - 1 ] * m return maximumProfit( 0 , queries, dp) # Driver code N = 5 queries = [ [ 1 , 4 , 5 ], [ 0 , 2 , 3 ], [ 3 , 4 , 5 ], [ 0 , 3 , 6 ] ] # Function call print (maximizeTheProfit(N, queries)) |
C#
using System; using System.Collections.Generic; class GFG { // Finding the maximum profit by businessman static int MaximumProfit( int idx, List< int []> queries, int [] dp) { if (idx == queries.Count) return 0; if (dp[idx] != -1) return dp[idx]; int notTake = MaximumProfit(idx + 1, queries, dp); int low = idx + 1, high = queries.Count - 1; int nextIdx = queries.Count; // Finding the idx for the next offer // if we take idx as the current offer while (low <= high) { int mid = (low + high) / 2; if (queries[mid][0] > queries[idx][1]) { high = mid - 1; nextIdx = mid; } else { low = mid + 1; } } // Performing this & use binary search // to find the next idx to perform int take = queries[idx][2] + MaximumProfit(nextIdx, queries, dp); return dp[idx] = Math.Max(take, notTake); } // Function to initiate maximum profit function static int MaximizeTheProfit( int n, List< int []> queries) { int m = queries.Count; queries.Sort((a, b) => a[0].CompareTo(b[0])); int [] dp = new int [m]; for ( int i = 0; i < m; i++) { dp[i] = -1; } return MaximumProfit(0, queries, dp); } public static void Main( string [] args) { int N = 5; List< int []> queries = new List< int []> { new int [] {1, 4, 5}, new int [] {0, 2, 3}, new int [] {3, 4, 5}, new int [] {0, 3, 6} }; // Function call Console.WriteLine(MaximizeTheProfit(N, queries)); } } |
Javascript
// Finding the maximum profit by businessman function maximumProfit(idx, queries, dp) { // Base case: if all offers are processed if (idx === queries.length) return 0; // If the result is already calculated, return it if (dp[idx] !== -1) return dp[idx]; // Calculate the profit if the current offer is not taken let notTake = maximumProfit(idx + 1, queries, dp); let low = idx + 1; let high = queries.length - 1; let nextIdx = queries.length; // Finding the index for the next offer if the current offer is taken while (low <= high) { let mid = Math.floor((low + high) / 2); if (queries[mid][0] > queries[idx][1]) { high = mid - 1; nextIdx = mid; } else { low = mid + 1; } } // Calculate the profit if the current offer is taken and find the maximum profit let take = queries[idx][2] + maximumProfit(nextIdx, queries, dp); dp[idx] = Math.max(take, notTake); return dp[idx]; } // Function to initiate the maximum profit function function maximizeTheProfit(n, queries) { // Sorting the queries based on the starting time queries.sort((a, b) => a[0] - b[0]); let m = queries.length; let dp = new Array(m).fill(-1); // Array to store computed results return maximumProfit(0, queries, dp); // Start computation } // Driver code let N = 5; let queries = [ [1, 4, 5], [0, 2, 3], [3, 4, 5], [0, 3, 6] ]; // Function call to find the maximum profit console.log(maximizeTheProfit(N, queries)); |
8
Time Complexity: O(M log M), where M is the size of queries[][] array.
Auxiliary Space: O(M)
Contact Us