C++ DP + Binary Search
See my latest update in repo LeetCode\n## Solution 1. DP + Binary Search\n\nIntuition: Almost the same as the classic problem 1235. Maximum Profit in Job Schedu
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n## Solution 1. DP + Binary Search\n\n**Intuition**: Almost the same as the classic problem [1235. Maximum Profit in Job Scheduling (Hard)](https://leetcode.com/problems/maximum-profit-in-job-scheduling/).\n\n**Algorithm**:\n* Sort the array in descending order of `start`.\n* Store the maximum profit we can get in range `[start, Infinity)` in a `map<int, long long> m`.\n* For each `A[i]`, `m[start[i]]` is either:\n  * The maximum profit we\'ve seen thus far.\n  * Or, `profit[i] + (end[i] - start[i]) + P(end[i])`, where `P` is the maximum profit we can get in range `[end[i], Infinity)`. We can get this `P` value by binary searching the map `m` -- `P(end[i]) = m.lower_bound(end[i])->second`.\n\n```cpp\n// OJ: https://leetcode.com/contest/biweekly-contest-61/problems/maximum-earnings-from-taxi/\n// Author: github.com/lzl124631x\n// Time: O(NlogN)\n// Space: O(N)\nclass Solution {\npublic:\n    long long maxTaxiEarnings(int n, vector<vector<int>>& A) {\n        sort(begin(A), end(A), [](auto &a, auto &b) { return a[0] > b[0]; }); // Sort the array in descending order of `start`\n        map<int, long long> m{{INT_MAX,0}}; // `dp` value. A mapping from a `start` point to the maximum profit we can get in range `[start, Infinity)`\n        long long ans = 0;\n        for (auto &r : A) {\n            int s = r[0], e = r[1], p = r[2];\n            m[s] = max(ans, p + e - s + m.lower_bound(e)->second);\n            ans = max(ans, m[s]);\n        }\n        return ans;\n    }\n};\n```
[]