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 businessmanint 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 functionint 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 codeint 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)); }} |
8
Time Complexity: O(M log M), where M is the size of queries[][] array.
Auxiliary Space: O(M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
