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;
}
};