[Python] dp with binary search, explained
This problem is very similar to problem 1235. Maximum Profit in Job Scheduling. The only difference is what profit we have given our ride: it is calculated as r
This problem is very similar to problem **1235.** Maximum Profit in Job Scheduling. The only difference is what profit we have given our ride: it is calculated as `rides[k][2] - rides[k][0] + rides[k][1]`.\n\n#### Complexity\nIt is `O(m log m)`, where `m = len(rides)`.\n\n#### Code\n```python\nimport bisect\n\nclass Solution:\n    def maxTaxiEarnings(self, n, rides):\n        rides = sorted(rides)\n        S = [i[0] for i in rides]\n        \n        m = len(rides)\n        dp = [0]*(m+1)\n        for k in range(m-1, -1, -1):\n            temp = bisect_left(S, rides[k][1])\n            dp[k] = max(dp[k+1], rides[k][2] - rides[k][0] + rides[k][1] + dp[temp])\n            \n        return dp[0]\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Binary Search', 'Dynamic Programming']