Brute Force Recursion -> Memoization -> Memoization + BinarySearch
Brute Force Intuition + Approach\n1. Sort rides array by pickup time, break ties by dropoff time\n2. Start from ride[0] with earliest pickup time, then recursiv
# Brute Force Intuition + Approach\n1. Sort rides array by pickup time, break ties by dropoff time\n2. Start from `ride[0]` with earliest pickup time, then recursively choose to \n- take the current ride\'s profit\n- Or choose to not not take it\n\nThere is one condition wether you can take the ride or not\nand be able to take the profit, and that is \nit must not conflict with any other rides you have picked up so far.\n3. From the current ride, find the next earliest ride that does not have a conflict. Because we sorted the array by pickup time, we just need to find the ride which has a `pickup_time >= current_ride_drop_off_time`\n\n# Complexity\n- Time complexity:\n```\n  O(nlogn) +     O(n      *       2^n) = O(n2^n)\n  sorting      finding       take ride\n              nextRide      or not take\n                        i.e. 2 possibilities \n                          each recursion,\n                          and depth is n\n\n```\n\n- Space complexity: `O(n) stack space`\n\n# Code\n```\n  public long maxTaxiEarnings(int n, int[][] rides) {\n    Arrays.sort(rides, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);\n\n    // Start from rides[0] with earliest pickup time\n    return recurse(rides, 0);\n  }\n\n  public long recurse(int[][] rides, int currentRide) {\n    int n = rides.length;\n    // we have considered all possibilities for each ride,\n    // return 0 profit\n    if (currentRide >= n)\n      return 0;\n\n    // From the current ride\'s dropoff,\n    // find the next earliest ride who has a pickup with no a conflict\n    int nextRide;\n    for (nextRide = currentRide + 1; nextRide < n; nextRide++) {\n      int nextRidePickup = rides[nextRide][0];\n      int currRideDropoff = rides[currentRide][1];\n\n      if (nextRidePickup >= currRideDropoff)\n        break;\n    }\n\n    int pickup = rides[currentRide][0];\n    int dropoff = rides[currentRide][1];\n    int tip = rides[currentRide][2];\n    long profit = dropoff - pickup + tip;\n\n    // nextRide may be within the rides array range,\n    // or there is no valid ride, in which nextRide is assigned value n\n    long profitIfTaken = profit + recurse(rides, nextRide);\n    long profitIfNotTaken = recurse(rides, currentRide + 1);\n\n    return Math.max(\n      profitIfTaken,\n      profitIfNotTaken\n    );\n  }\n```\n\n# Brute Force with Caching - Memoization Intuition\nSame idea as brute force, except we add a cache every recursion,\nto avoid making the same recursive calls over and over on\nthe same input parameter (`currentRide`).\n\n# Complexity\n- Time complexity:\n```\nO(nlogn) + O(      n       x   n )  = O(n^2)\n sorting     finding the      because of caching,\n             next ride       2^n is bounded to n now,\n                            because of caching\n                            limited to size n\n```\n- Space complexity: `O(n) stack space + cache size`\n\n# Code\n\n```\n  private static final long CACHE_MISS = -1L;\n\n  public long maxTaxiEarnings(int n, int[][] rides) {\n    Arrays.sort(rides, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);\n    long[] cache = new long[rides.length];\n    Arrays.fill(cache, CACHE_MISS);\n    return recurse(rides, 0, cache);\n  }\n\n  public long recurse(int[][] rides, int currentRide, long[] cache) {\n    int n = rides.length;\n    if (currentRide >= n)\n      return 0;\n    \n    if (cache[currentRide] != CACHE_MISS)\n      return cache[currentRide];\n\n    int pickup = rides[currentRide][0];\n    int dropoff = rides[currentRide][1];\n    int tip = rides[currentRide][2];\n    long profit = dropoff - pickup + tip;\n\n    int nextRide;\n    for (nextRide = currentRide + 1; nextRide < n; nextRide++) {\n      int nextRidePickup = rides[nextRide][0];\n      int currRideDropoff = rides[currentRide][1];\n\n      if (nextRidePickup >= currRideDropoff)\n        break;\n    }\n\n    long profitIfTaken = profit + recurse(rides, nextRide, cache);\n    long profitIfNotTaken = recurse(rides, currentRide + 1, cache);\n\n    return cache[currentRide] = Math.max(\n      profitIfTaken,\n      profitIfNotTaken\n    );\n  }\n```\n\n# Optimization with binary search and building on top of previous approach\nSame idea as memoization, except we find the next ride using binary search instead of linear, sequential for loop.\n\n# Complexity\n- Time complexity:\n```\nO(nlogn) + O(      logn       x   n )             =  O(nlogn)\n sorting     finding the      because of caching,\n             next ride       2^n is bounded to n now,\n                            because of caching\n                            limited to size n\n```\n- Space complexity: `O(n) stack space + cache size`\n\n\n# Code\n```\nclass Solution {\n\n  private static final long CACHE_MISS = -1L;\n\n  public long maxTaxiEarnings(int n, int[][] rides) {\n    Arrays.sort(rides, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);\n    long[] cache = new long[rides.length];\n    Arrays.fill(cache, CACHE_MISS);\n    return recurse(rides, 0, cache);\n  }\n\n  public long recurse(int[][] rides, int currentRide, long[] cache) {\n    int n = rides.length;\n    if (currentRide >= n)\n      return 0;\n    \n    if (cache[currentRide] != CACHE_MISS)\n      return cache[currentRide];\n\n    int pickup = rides[currentRide][0];\n    int dropoff = rides[currentRide][1];\n    int tip = rides[currentRide][2];\n    long profit = dropoff - pickup + tip;\n\n    int nextRide = binarySearch(rides, dropoff, currentRide + 1, n - 1);\n    for (nextRide = currentRide + 1; nextRide < n; nextRide++) {\n      int nextRidePickup = rides[nextRide][0];\n      int currRideDropoff = rides[currentRide][1];\n\n      if (nextRidePickup >= currRideDropoff)\n        break;\n    }\n\n    long profitIfTaken = nextRide >= 0 ? profit + recurse(rides, nextRide, cache) : profit;\n    long profitIfNotTaken = recurse(rides, currentRide + 1, cache);\n\n    return cache[currentRide] = Math.max(\n      profitIfTaken,\n      profitIfNotTaken\n    );\n  }\n\n  public int binarySearch(int[][] rides, int dropoff, int l, int r) {\n    int result = -1;\n    while (l <= r) {\n      int nextRide = l + (r - l) / 2;\n      int nextRidePickup = rides[nextRide][0];\n\n      if (nextRidePickup >= dropoff) {\n        result = nextRide;\n        r = nextRide - 1;\n      } else {\n        l = nextRide + 1;\n      }\n    }\n\n    return result;\n  }\n}\n```
['Java']