Description

Submission

class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        sort(offers.begin(), offers.end(), [](auto& v1, auto& v2) {
            return v1[1] < v2[1];
        });

        int m = offers.size();

        vector<int> dp(n, 0);

        for(int i = 0, idx = 0; i < n; ++i) {            
            for ( ; idx < m && offers[idx][1] == i; idx++) {
                
                int start = offers[idx][0];
                int end = offers[idx][1];
                int gold = offers[idx][2];
                if (start - 1 >= 0) {
                    dp[end] = max(dp[end], dp[start-1] + gold);
                } else {
                    dp[end] = max(dp[end], gold);
                }   
            }

            if (i - 1 >= 0)
                dp[i] = max(dp[i-1], dp[i]);
        }

        return dp.back();
    }
};