Description

Submission

class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        sort(rides.begin(), rides.end(), [](auto& a, auto& b) {
            return a[1] < b[1];
        });

        map<int, long long> dp;
        dp[0] = 0;
        long long ret = 0;
        for(auto& ride: rides) {
            auto it = dp.upper_bound(ride[0]);
            if(it != dp.begin()) {
                --it;
                dp[ride[1]] = max(it->second - ride[0] + ride[1] + ride[2], ret);
            }
            ret = max(dp[ride[1]], ret);
        }
        return ret;
    }
};

// dp[x]: the maximum money can get when ending with x
// dp: should be non-decreasing