Maximum Earnings From Taxi — LeetCode 2008 Python Solution

The 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.

Example

Input

n = 5, rides = [[2,5,4],[1,5,1]]

Output

7

Explanation

We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

Python solution

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(rides):
                return 0
            st, ed, tip = rides[i]
            j = bisect_left(rides, ed, lo=i + 1, key=lambda x: x[0])
            return max(dfs(i + 1), dfs(j) + ed - st + tip)

        rides.sort()
        return dfs(0)

Complexity

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 2008. Maximum Earnings From Taxi is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Related problems