Multiple solutions with detailed thought process (quadratic - TLE, binary search and optimal)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n  """\n  We can see that this is an optimization problem that is asking us to maximize the money that we can get\n  by moving passengers. At a time, there can only be one passenger in our taxi. This hints us to go in the \n  brute force, careful brute force (dynamic programming by eliminating overlapping subproblems, providing we\n  can prove that an optimal substructure exists in our recurrence relation) or a greedy solution.\n\n  Let\'s see how we can approach this in a brute force way:\n  If we are looking at a passenger i, there are multiple choices we have, we can either choose this passenger, \n  or we can choose any other passenger that\'s overlapping with this one. So, let\'s try all the passengers. \n  Let\'s sort the rides by their end points (we\'ll look at it from right to left). Let\'s say i and i-1 have an overlap.\n  If we pick ith passenger, then we need to solve the subproblem for i-2 passenger. If we pick the (i-1)st passenger, \n  we again need to solve the subproblem for i-2 (i-2 and i-1 don\'t have an overlap). So, there are overlapping \n  subproblems, which we can eliminate by dynamic programming.\n\n  Let\'s define our recurrence relation as:\n  f(i) = the max earning that we can get from rides 1...i\n  Mathematically:\n  f(i) = max [ f(i-1), f(i-j) + earning(i) ], j = the first ride from end that doesn\'t overlap with the ith ride\n\n  The number of total subproblems to solve will be the same as the number of rides. So we can create a 1d table\n  of size len(rides) + 1, with table[0] as the base case where there are no rides so 0 money is to be made.\n\n  Each subproblem f(i) depends only on the values of i to the left, so there is a top-sort order which allows us\n  to solve subproblems incrementally from i=1 to i=len(rides)+1. At the end of this the answer would be in \n  table[len(rides)] (or in other words, the max earning from rides 1...len(rides))\n\n\n  Now on to implementation:\n  1. If we implementing the recurrence as is i.e. with two for loops (the inner for loop looks for the non overlapping\n  ride), we run into Time limit exceeded error. T(n) = O(#rides^2)\n\n  2. We can overcome that with using binary search (since all the rides are sorted by their end times). You can see \n  both the implementations below. T(n) = O(#rides * log(#rides))\n\n\n  So far in the above implementation, we haven\'t used "n". I was not sure what\'s the purpose of that. Then, I came \n  across a solution (https://leetcode.com/problems/maximum-earnings-from-taxi/solutions/1470935/c-python-dp-o-m-n-clean-concise/), that helped me understand how this solution could be improved further. \n  \n  Instead of looking at the rides, we can look at each point and define the recurrence (in a similar way) as:\n  f(i) = the max earning that we can get by finishing at point i.\n  Mathematically:\n  f(i) = max [ f(i-1), f(i-j) + reward(i) for all the rides that end at i ]\n  \n  With this recurrence, the max subproblems are n. And we can solve them in a similar way from left to right. But,\n  before implementing the recurrence we need to create a map so that we can easily get all the rides that end at \n  a particular point.\n  This processes all the n points, and only processes each ride only once. So gives a total of O(n + #rides) solution.\n\n  Hope this is helpful to someone!\n  """\n\n  # The optimal solution\n  def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n    ridesEndingAt = defaultdict(list)\n    for ride in rides:\n      start, end, tip = ride\n      ridesEndingAt[end].append([start, end-start+tip])\n    \n    table = [0]*(n+1)\n    for i in range(1, n+1):\n      # If we don\'t choose the rides ending at point i\n      maxEarningWithoutAnyRideEndingAti = table[i-1]\n\n      # If we choose the rides ending at point i, then for all the rides that end at this point\n      # we look for their starting point, and get the max earning up to that point. And then, among those\n      # rides, we choose the ride that gets us the maximum earning\n      maxEarningFromRide = 0\n      for rideEdningAti in ridesEndingAt[i]:\n        startPoint, earningFromTheRide = rideEdningAti\n        maxEarningFromRide = max(maxEarningFromRide, earningFromTheRide + table[startPoint])\n      \n      maxEarning = max(maxEarningWithoutAnyRideEndingAti, maxEarningFromRide)\n      table[i] = maxEarning\n    return table[-1]\n\n\n  # Improving performance with binary search\n  def maxTaxiEarningsBinarySearch(self, n: int, rides: List[List[int]]) -> int:\n    total_rides = len(rides)\n    rides.sort(key=lambda x:x[1])\n    table = [0]*(len(rides)+1)\n    \n    for i in range(1, len(rides) + 1):\n      # Fill in table[i]\n      currRide = rides[i-1]\n      \n      # If we don\'t choose the current ride\n      maxEarningWithoutCurrentRide = table[i-1]\n      \n      # If we choose the current ride\n      earningUpToPrevRide = 0\n      low, high = 0, i-2\n      while low <= high:\n        mid = low + (high - low) // 2\n        # Find the first ride that has end point before the start point of the current ride\n        midRide = rides[mid]\n        if midRide[1] <= currRide[0]:\n          low = mid + 1\n        else:\n          high = mid - 1\n      # high is pointing to the first ride that has end point before the start point of the current ride.\n      earningUpToPrevRide = table[high+1]\n      currentRideEarning = currRide[1] - currRide[0] + currRide[2]\n      \n      table[i] = max(maxEarningWithoutCurrentRide, currentRideEarning + earningUpToPrevRide)\n    return table[-1]\n\n  def maxTaxiEarningsQuadratic(self, n: int, rides: List[List[int]]) -> int:\n    total_rides = len(rides)\n    rides.sort(key=lambda x:x[1])\n    table = [0]*(len(rides)+1)\n\n    for i in range(1, total_rides+1):\n      # Fill in table[i]\n      currRide = rides[i-1]\n\n      # If we don\'t choose currRide, max earning is the same as table[i-1]\n      maxEarningWithoutCurrentRide = table[i-1]\n\n      # If we choose currRide, max earning would be the earning from the current ride plus the \n      # earning from the last ride that didn\'t overlap with the current ride\n      currRideEarning = currRide[1] - currRide[0] + currRide[2]\n      earningUpToLastRide = 0\n      for j in range(i-2, -1, -1):\n        prevRide = rides[j]\n        if prevRide[1] <= currRide[0]:\n          # We found the last ride that doesn\'t overlap with current ride\n          earningUpToLastRide = table[j+1] # index into table is 1 + the ride index\n          break\n      \n      table[i] = max(maxEarningWithoutCurrentRide, currRideEarning + earningUpToLastRide)\n\n    return table[-1]\n\n\n  # For this method, we defined the recurrence slightly differently. \n  # f(i) = the max earning that we make if we select the ith ride.\n  # In the end, the max of the DP table is the max earning.\n  def maxTaxiEarnings2(self, n: int, rides: List[List[int]]) -> int:\n    rides.sort(key=lambda x:x[1])\n    table = [0]*n\n    table[0] = rides[0][1] - rides[0][0] + rides[0][2]\n\n    for i in range(1, len(rides)):\n      reward = rides[i][1] - rides[i][0] + rides[i][2]\n      prevReward = 0\n      for j in range(0, i):\n        if rides[j][1] <= rides[i][0]:\n          prevReward = max(prevReward, table[j])\n      table[i] = prevReward + reward\n    \n    return max(table)\n```
['Binary Search', 'Dynamic Programming', 'Python3']