C++ | O(N*logN) | suffix array + binary search
\ntypedef long long ll;\nclass Solution {\npublic:\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<pair<ll, pair<ll, ll>>> i
```\ntypedef long long ll;\nclass Solution {\npublic:\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<pair<ll, pair<ll, ll>>> intv;\n        vector<ll> earn(rides.size());\n        vector<ll> startTime;\n        \n        for(int i=0; i<rides.size(); i++){\n            intv.push_back({rides[i][0], {rides[i][1], \n                            (ll)rides[i][2] + (ll)rides[i][1] - (ll)rides[i][0]}});\n            startTime.push_back(rides[i][0]);\n        }\n        \n        sort(intv.begin(), intv.end());\n        sort(startTime.begin(), startTime.end());\n        \n        ll ret = 0;\n        for(int i=intv.size()-1; i >= 0; i--){\n            earn[i] = intv[i].second.second;\n            \n            // find k > i with start_point[k] > end_point[i] and maximum earning \n            // for maximum earning maintain suffix array\n            if(i+1 < intv.size()){\n                int k = lower_bound(startTime.begin()+i+1, startTime.end(), intv[i].second.first) \n                    - startTime.begin();\n                if(k < intv.size())\n                    earn[i] = max(earn[i], intv[i].second.second + earn[k]);\n            }\n            \n            ret = max(ret, earn[i]);\n            \n            // suffix max computation\n            if(i+1 < intv.size())\n                earn[i] = max(earn[i], earn[i+1]);\n        }\n        \n        return ret;\n    }\n};\n```
[]