Problem¶

There are n points on a road you are driving your taxi on. The n points on the road are labeled from 1 to n in the direction you are going, and you want to drive from point 1 to point n to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a 0-indexed 2D integer array rides, where rides[i] = [starti, endi, tipi] denotes the ith passenger requesting a ride from point starti to point endi who is willing to give a tipi dollar tip.

For each passenger i you pick up, you earn endi - starti + tipi dollars. You may only drive at most one passenger at a time.

Given n and rides, return the maximum number of dollars you can earn by picking up the passengers optimally.

Note: You may drop off a passenger and pick up a different passenger at the same point.

Example 1:

**Input:** n = 5, rides = [[2,5,4],[1,5,1|2,5,4],[1,5,1]]
**Output:** 7
**Explanation:** We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

Constraints:

• 1 <= n <= 10**5
• 1 <= rides.length <= 3 * 10**4
• rides[i].length == 3
• 1 <= start_i < end_i <= n
• 1 <= tip_i <= 10**5

Solve¶

This need some Dynamic programming

Minimize memory allocation solution¶

• Closely related to 1751. Maximum Number of Events That Can Be Attended II, where I use a binary search to stored best found choosing rides/events with each end at position index. Storing it it in a lookup array, we have either:
  • (Case 1) Last found best rides array lookup[end] = lookup[end-1]
  • (Case 2) Choosing current ride and best found [..., end] with end < start[index]. lookup[end] = value_of_the_ride + lookup[start-1]

end-1 or start-1 here is just for representation, as I try to minimize the total memory for the lookup array by using Binary search instead.

• Sorting: To get the best result, any possible ride we can take between two ride in (Case 2) need to already process. so we need to sort rides array by end to make sure our calculated in a right order.
• Storing: With two array key, and lookup which is where we save the current end and total value of the path (now tbh, key isn’t doing that much as it just a better way to get [r[1] for r in rides[:index]]),

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        def sort_key_end(x):
            return x[1]

        def binary_search(arr, value):
            l = -1
            r = len(arr)
            while l+1<r:
                m = (l + r) //2
                curr_val = arr[m]
                if curr_val <= value:
                    l = m
                else:
                    r = m
            is_found = l > -1
            return is_found, l

        rides.sort(key=sort_key_end)
        lookup = []
        key = []
        for index, (s, e, v) in enumerate(rides):
            lookup.append(e - s + v)
            key.append(e)
            is_found, possible = binary_search(key, s)
            if is_found:
                lookup[index] += lookup[possible]
            if lookup[index] < lookup[index - 1]:
                lookup[index] = lookup[index - 1]

        return lookup[len(rides)-1]

Using hash map to sort instead¶

We can using a hash map with dict() instead for better sorting in O(n) time complexity and O(1) look up too, here is a lazy Crtl + C implementation:

• This sorted rides by start instead (which making you need to go backward from end to start instead)
• The checking parse get all possible (case 2) at current position, find the max one with max(dp[i], dp[e] + d), after all of that, recheck (case 1) with final update dp[i] = max(dp[i], dp[i + 1])
  

  class Solution:
      def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
          rideStartAt = defaultdict(list)
          for s, e, t in rides:
              rideStartAt[s].append([e, e - s + t])
          dp = [0] * (n + 1)
          for i in range(n - 1, 0, -1):
              for e, d in rideStartAt[i]:
                  dp[i] = max(dp[i], dp[e] + d)
              dp[i] = max(dp[i], dp[i + 1])
  
          return dp[1]
  

Quick rewrite it again, yeah, same thing.

from typing import List
from collections import defaultdict


class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rideStartAt = defaultdict(list)
        for start, end, tip in rides:
            rideStartAt[start].append([end, end - start + tip])
        lookup = [0] * (n + 1)
        for i in range(n - 1, 0, -1):
            for end, true_value in rideStartAt[i]:
                lookup[i] = max(lookup[i], lookup[end] + true_value)
            lookup[i] = max(lookup[i], lookup[i + 1])

        return lookup[1]

We just storing in a normal array instead of using binary search

My first implementation is affected by 1751. Maximum Number of Events That Can Be Attended II, the binary search part isn’t necessary and increasing a lot of computed time.

Here is implementation my re implementation which lookup is an array with its range is base on n (the worst case it is only [0..10**5]). Which return the Accepted with 1550 ms

class Solution_2:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        def sort_key_end(x):
            return x[1]

        rides.sort(key=sort_key_end)
        lookup = [0] * (n + 1)
        car_pos = 1
        for s, e, v in rides:
            for i in range(car_pos, e):
                lookup[i] = lookup[car_pos]
            car_pos = e
            possible = (e - s + v)
            if s > 0:
                possible += lookup[s]
            lookup[e] = max(lookup[e], lookup[e-1], possible)

        return lookup[car_pos]

Looking for the best of best implementation?¶

Here is sample 1542 ms submission

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort(key=lambda r: r[1])
        cur = [-1]
        dollars = [0]

        for st, ed, tip in rides:
            i = bisect_right(cur, st)
            earn = dollars[i - 1] + ed - st + tip
            dollars.append(max(dollars[-1], earn))
            cur.append(ed)
        return dollars[-1]

Python isn’t that fast, so anything that you get from standard library will get you quite far on the leader board. bisect_right being use here is a python array helper function that alternate Binary search implementation.

• There is a lot of similarity to the first implementation. My retry on rewriting the same function
  

  class Solution:
      def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
          def sort_key_end(x):
              return x[1]
  
          rides.sort(key=sort_key_end)
          key = [-1]
          lookup = [0]
  
          for start, end, tip in rides:
              search = bisect_right(key, start)
              true_rides_value = lookup[search - 1] + end - start + tip
              lookup.append(max(lookup[-1], true_rides_value))
              key.append(end)
          return lookup[-1]
  

Final result¶