✔ Python Solution | DP | 2 Solutions
Solution 1\n\nTime : O(n)\nSpace : O(n)\n\n\nclass Solution:\n    def maxTaxiEarnings(self, n, A):\n        A.sort()\n        dp = [0] * (n+1)\n        for i in
**Solution 1**\n\n```Time``` : ```O(n)```\n```Space``` : ```O(n)```\n\n```\nclass Solution:\n    def maxTaxiEarnings(self, n, A):\n        A.sort()\n        dp = [0] * (n+1)\n        for i in range(n-1,-1,-1):\n            dp[i] = dp[i+1]\n            while A and i == A[-1][0]:\n                s,e,t = A.pop()\n                dp[i] = max(dp[i],dp[e] + e + t - s)\n        return dp[0]\n```\n\n**Solution 2**\n\n```Time``` : ```O(kLog(k))```\n```Space``` : ```O(k)```\n\n```\nclass Solution:\n    def maxTaxiEarnings(self, n, A):\n        A.sort(key = lambda x:x[1])\n        dp = [(0,0)]\n        for s,e,t in A:\n            i = bisect.bisect(dp,s, key = lambda x:x[0]) - 1\n            profit = e + t - s + dp[i][1]\n            if profit > dp[-1][1]:\n                dp.append((e , profit))\n        return dp[-1][1]\n```
['Dynamic Programming', 'Binary Tree', 'Python']