c++ O(n) dp solution adn O(nlgn) BIT Tree solution
O(n) dp solution \n\nclass Solution {\npublic:  \n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<vector<pair<int,int>>> tmp(
# O(n) dp solution \n```\nclass Solution {\npublic:  \n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<vector<pair<int,int>>> tmp(n+1);\n        for(auto& r : rides) {\n            tmp[r[1]].push_back({r[0], r[1] - r[0] + r[2]});\n        } \n        long long ret = 0; \n        vector<long long> dp(n+1);\n        for(int i = 1;i<=n;i++) {\n            for(auto&& t : tmp[i]) {\n                dp[i] = max(dp[i],dp[t.first] + t.second);\n            }\n            dp[i] = max(dp[i-1],dp[i]);\n        }\n        return dp.back();\n    }\n};\n```\n\n# O(nlgn) bit tree solution \n``` \nclass Solution {\npublic:\n    \n    int lastOne(int x) {\n        return x &(-x);\n    }\n    \n    long long req(vector<long long>& bits, int i) {\n        long long ret = 0;; \n        for(;i;i-=lastOne(i)) {\n            ret = max(ret,bits[i]);\n        }\n        return ret; \n    }\n    \n    void update(vector<long long>& bits, int i, long long v) {\n        for(;i<bits.size();i+=lastOne(i)) {\n            bits[i] = max(bits[i],v);\n        }\n    }\n    \n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<long long> bits(n + 10);\n        sort(rides.begin(),rides.end(),[](auto& a, auto& b) {\n            return a[0] < b[0];\n        });\n        long long ret = 0; \n        for(auto&& r : rides) {\n            long long t = req(bits,r[0]);\n            long long total_gain = t + r[1] - r[0] + r[2];\n            update(bits,r[1],total_gain);\n            ret = max(ret, total_gain);\n        }\n        return ret; \n    }\n};\n```
[]