Description

Submission

class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        int n = events.size();
        vector<vector<int>> dp(n+1, vector<int>(k+1));
        sort(events.begin(), events.end(), [](auto& a, auto& b) {
            return a[1] < b[1];
        });
        events.insert(events.begin(), events[0]);
        vector<int> endTimes({0});

        for(int i = 0; i <= n; ++i) {
            dp[i][0] = 0;
        }

        int ret = 0;
        for(int i = 1; i <= n; ++i) {
            int t = lower_bound(endTimes.begin(), endTimes.end(), events[i][0]) - 1 
                            - endTimes.begin();
            for(int j = 1; j <= k; ++j) {
                dp[i][j] = max(dp[i-1][j], dp[t][j-1] + events[i][2]);
                ret = max(ret, dp[i][j]);
            }
            endTimes.push_back(events[i][1]);
        }
        return ret;
    }
};

// dp[x][i]: the maximum value ending with index x, in i events