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!
