Untitled

class Solution {
public:

    long long dp[100001];
    static bool compare(vector<int> &a, vector<int> &b) {
        if(a[0]<b[0]) {
            return true;
        } else if (a[0]> b[0]) {
            return false;
        } else {
            if(a[1]<b[1]) {
                return true;
            } else if(a[1]>b[1]) {
                return false;
            } else {
                return a[2]<b[2];
            }
        }

    
    }                                                                                                                                                                

    int find(int dest, int n , vector<vector<int>> &rides) {
        int low = 0;
        int high = n-1;
        int ans = -1;
        while(low<=high) {
            int mid = low + (high-low)/2;
           
            if(rides[mid][0]>=dest) {
                ans = mid;
                high = mid-1;
            } else {
                low = mid+1;
            }
        }
        
        return ans;
    }

    long long recur(int index, int n, vector<vector<int>>& rides) {
        if(index==n)
        return 0;
        if(index==-1)
        return 0;
        if(dp[index]!=-1)
        return dp[index];
       

        int dest = find(rides[index][1], n, rides);
        //cout<<"dest:"<< dest<<endl;
        long long skipCur = recur(index+1, n, rides);
        long long withCur = rides[index][1]-rides[index][0]+rides[index][2] + recur(dest, n, rides);

       dp[index]= max(skipCur, withCur);
       return dp[index];



    }

    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        sort(rides.begin(), rides.end());
        memset(dp, -1, sizeof(dp));
        // for(auto it: rides) {
        //     cout<<it[0]<<" "<<it[1]<<" "<<it[2]<<endl;
        // }

        return recur(0, rides.size(), rides);
        

        return 0;
    }
};