Untitled

class Solution {
public:
    int knapsack_recursion( vector<vector<int>>& offers, int pos, int n, vector<int>& dp)
    {
        if(pos >= n)
            return 0;

        if (dp[pos] != -1)
            return dp[pos];
        
        auto compareSecondElement = [](int b, vector<int>& a) {
            return b < a[0];
        };
        
        auto upperBoundIt = upper_bound(offers.begin(), offers.end(), offers[pos][1], compareSecondElement);

        dp[pos] = max(offers[pos][2] + knapsack_recursion(offers, upperBoundIt - offers.begin(), n, dp),
                knapsack_recursion(offers, pos + 1, n, dp));

        return dp[pos];
    }
    
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        sort(offers.begin(), offers.end());
        vector<int> dp = vector<int>(offers.size() + 1,-1);
        int res = knapsack_recursion(offers, 0, offers.size(), dp);
        return res;
    }
};