python3 sorting+dynamic programming(with explicit explanation + test case)
Intuition\nthis question is similar to leetcode 80: maximum number of events that can be attended, the two question uses simiar sorting and usage of stack/heap.
# Intuition\nthis question is similar to [leetcode 80: maximum number of events that can be attended](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/), the two question uses simiar sorting and usage of stack/heap. In this solution, I used dynamic programming to use an array to keep track of whats the maximum amount of money the driver has made by the time he switched to direction ```i```\n\n# Approach\nfirst we sort the rides based on the end direction, and break ties using the starting direction. In Python3, we can do the sorting using ```rides = sorted(rides, key=lambda x: (x[1], x[0]))```\n\nnext we build a array of size ```n+1``` to keep track of whats the maximum amount of money the drive can make by the time he switched to direction ```i```\n\nthen we began the algorithm\'s iterative part where we iterate over each direction, at each direction we store in our stack the rides that ends in current direction, then the maximum money the driver can make at index ```i``` is ```dp[i] = max(dp[start]+end-start+tip, dp[d])```\n\nthen in the end, compare the current ```dp[i]``` with previous value ```dp[i-1]```, and set ```dp[i] = max(dp[i], dp[i-1])```\n\nfor a detailed example, for test case:\n```sol = Solution()\nn = 10\nrides = [[2,3,6],[8,9,8],[5,9,7],[8,9,1],[2,9,2],[9,10,6],[7,10,10],[6,7,9],[4,9,7],[2,3,1]]\n```\n\nafter sorting, rides becomes:\n```\nrides = [[2, 3, 6], [2, 3, 1], [6, 7, 9], [2, 9, 2], [4, 9, 7], [5, 9, 7], [8, 9, 8], [8, 9, 1], [7, 10, 10], [9, 10, 6]]\n```\n\nthe dp array looks like this:\n```\ndp = [0, 0, 0, 7, 7, 7, 7, 17, 17, 26, 33]\n```\n\nthen we simply ```return max(dp)```\n\n# Complexity\n- Time complexity:\nlet ```k = len(rides)```\n$$O(max(n, k))$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```python\nclass Solution:\n    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n        # rides based on the end direction, and break ties using the starting direction\n        rides = sorted(rides, key=lambda x: (x[1], x[0]))\n        l = []\n        dp = [0] * (n+1)\n        idx = 0\n\n        # iterate over each end direction\n        for d in range(1, n+1):\n\n            stack = []\n            # store all rides that ends up in current direction\n            while idx < len(rides) and rides[idx][1] == d:\n                stack.append(rides[idx])\n                idx += 1\n\n            # calculate the maximum money that can me made in current direction\n            while stack:\n                start, end, tip = stack.pop()\n                dp[d] = max(dp[d], dp[start]+end-start+tip)\n            # compare with last direction and keeping the maximum\n            dp[d] = max(dp[d], dp[d-1])\n        return max(dp)\n```\n\nif my solution has helped you, please consider upvoting my anwser, thank you :)\n\n
['Python3']