Problem Description

You are a taxi driver on a road with n points labeled from 1 to n. You start at point 1 and want to drive to point n in one direction only (you cannot go backwards).

Along the way, there are passengers waiting for rides. Each passenger is represented by [start_i, end_i, tip_i], meaning:

• They want a ride from point start_i to point end_i
• They will give you a tip_i dollar tip

When you pick up passenger i, you earn end_i - start_i + tip_i dollars (the distance traveled plus the tip).

Important constraints:

• You can only carry one passenger at a time
• You cannot change direction (always moving from point 1 toward point n)
• You can drop off one passenger and immediately pick up another at the same point

Given n (the number of points) and a list of rides (passenger requests), find the maximum amount of money you can earn by choosing which passengers to pick up optimally.

Example scenario: If you have passengers A and B where A wants to go from point 2 to 5 (with tip 3) and B wants to go from point 3 to 7 (with tip 5), you cannot take both since their rides overlap. You must choose which combination of non-overlapping rides gives you the most money.

The solution uses dynamic programming with memoization. After sorting rides by start point, for each ride position, it decides whether to take the current ride or skip it. If taken, it uses binary search to find the next possible ride that doesn't overlap (starts at or after the current ride's end point) and calculates the maximum earnings recursively.

Intuition

Think of this problem as making a series of decisions: for each potential ride, should we take it or skip it?

The key insight is that once we sort the rides by their starting points, we're essentially moving through them in the order we'd encounter them on our journey. This transforms the problem into a classic dynamic programming scenario where we need to make optimal choices at each step.

For any given ride at position i, we face two choices:

1. Skip this ride - Continue to the next available ride and see what maximum earnings we can get from there
2. Take this ride - Earn money from this ride, then find the next compatible ride we can take after dropping off this passenger

The challenge with option 2 is finding which rides are "compatible" after taking the current one. Since we can't carry multiple passengers simultaneously, we need to find rides that start at or after our current ride's end point. Because we've sorted the rides by start time, we can use binary search to efficiently find the first compatible ride.

This naturally leads to a recursive structure: the maximum earnings from position i equals the maximum of:

• Maximum earnings from position i + 1 (if we skip)
• Current ride's earnings + maximum earnings from the next compatible position (if we take it)

The formula becomes: dfs(i) = max(dfs(i + 1), earnings_from_ride_i + dfs(j)) where j is the index of the first ride that starts at or after the current ride's end point.

By using memoization, we avoid recalculating the same subproblems multiple times, making our solution efficient. The sorting step ensures we process rides in a logical order, and binary search helps us quickly find compatible subsequent rides, bringing the overall approach together elegantly.

Learn more about Binary Search, Dynamic Programming and Sorting patterns.

Solution Approach

The solution implements a dynamic programming approach with memoization and binary search optimization.

Step 1: Sort the rides

rides.sort()

We sort all rides by their starting points in ascending order. This ensures we process rides in the order we'd encounter them while traveling from point 1 to n.

Step 2: Define the recursive function with memoization

@cache
def dfs(i: int) -> int:

The dfs(i) function calculates the maximum earnings possible starting from the i-th ride. The @cache decorator provides memoization to avoid redundant calculations.

Step 3: Base case

if i >= len(rides):
    return 0

When we've considered all rides (index out of bounds), there's no more money to be earned, so return 0.

Step 4: Extract current ride information

st, ed, tip = rides[i]

Get the start point, end point, and tip for the current ride.

Step 5: Find the next compatible ride using binary search

j = bisect_left(rides, ed, lo=i + 1, key=lambda x: x[0])

Use bisect_left to find the first ride whose start point is greater than or equal to the current ride's end point (ed). The search starts from i + 1 (rides after the current one) and uses key=lambda x: x[0] to compare based on start points. This gives us index j of the first compatible ride if we take the current one.

Step 6: Make the optimal decision

return max(dfs(i + 1), dfs(j) + ed - st + tip)

Compare two options:

• dfs(i + 1): Skip the current ride and consider rides starting from the next position
• dfs(j) + ed - st + tip: Take the current ride (earning ed - st + tip dollars) and then optimally handle rides starting from position j

The function returns the maximum of these two choices.

Step 7: Start the recursion

return dfs(0)

Begin the process from the first ride (index 0) to get the maximum possible earnings.

The time complexity is O(n log n) for sorting plus O(m^2 log m) for the memoized recursion with binary search, where m is the number of rides. The space complexity is O(m) for the memoization cache.

Example Walkthrough

Let's walk through a small example with n = 7 and the following rides:

• Ride A: [1, 4, 2] - From point 1 to 4, tip $2 (earns 4-1+2 =$5)
• Ride B: [2, 5, 3] - From point 2 to 5, tip $3 (earns 5-2+3 =$6)
• Ride C: [5, 7, 1] - From point 5 to 7, tip $1 (earns 7-5+1 =$3)

Step 1: Sort rides by start point After sorting: [[1,4,2], [2,5,3], [5,7,1]] Let's index them as positions 0, 1, and 2.

Step 2: Begin recursion from position 0 We call dfs(0) to find the maximum earnings starting from the first ride.

Step 3: At position 0 (Ride A: [1,4,2]) We have two choices:

• Skip it: Call dfs(1) to see what we can earn from position 1 onward
• Take it: Earn $5, then find the next compatible ride
  • Using binary search: Find first ride starting at or after point 4
  • This gives us position 2 (Ride C starts at point 5)
  • So we calculate: $5 + dfs(2)

Step 4: Evaluate dfs(1) - Position 1 (Ride B: [2,5,3]) Two choices:

• Skip it: Call dfs(2)
• Take it: Earn $6, then find next compatible ride
  • Binary search finds position 2 (Ride C starts at point 5)
  • Calculate: $6 + dfs(2)

Step 5: Evaluate dfs(2) - Position 2 (Ride C: [5,7,1]) Two choices:

• Skip it: Call dfs(3) which returns 0 (no more rides)
• Take it: Earn $3, then call dfs(3) which returns 0
• Result: max(0, 3) = 3

Step 6: Backtrack and compute

• dfs(2) = 3
• dfs(1) = max(dfs(2), 6 + dfs(2)) = max(3, 6 + 3) = 9
• dfs(0) = max(dfs(1), 5 + dfs(2)) = max(9, 5 + 3) = 9

Final Answer: $9

The optimal strategy is to skip Ride A and take both Ride B and Ride C, earning $6 +$3 = $9. Note that if we had taken Ride A (earning$5), we couldn't take Ride B (they overlap), and could only add Ride C for a total of $8.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log m) where m is the length of rides.

The time complexity breaks down as follows:

• Sorting the rides array takes O(m × log m) time
• The DFS function with memoization visits each ride at most once due to the @cache decorator, resulting in O(m) unique function calls
• For each DFS call, we perform a binary search using bisect_left to find the next compatible ride, which takes O(log m) time
• Therefore, the total time for all DFS operations is O(m × log m)
• The overall time complexity is dominated by O(m × log m) from both sorting and the DFS traversal with binary search

Space Complexity: O(m) where m is the length of rides.

The space complexity consists of:

• The recursion call stack can go up to O(m) depth in the worst case when processing all rides sequentially
• The @cache decorator stores memoization results for up to O(m) different states (one for each possible starting index)
• The sorted rides array doesn't require additional space as it sorts in-place
• Therefore, the total space complexity is O(m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Binary Search Key Function

A common mistake is using the wrong comparison in the binary search when finding the next compatible ride.

Incorrect Implementation:

# Wrong: Comparing entire ride tuples instead of just start points
next_compatible_ride = bisect_left(rides, end_point, lo=ride_index + 1)

This fails because bisect_left would try to compare end_point (an integer) with entire ride tuples [start, end, tip], causing a TypeError or incorrect comparisons.

Correct Implementation:

# Correct: Using key function to extract start point for comparison
next_compatible_ride = bisect_left(
    rides, 
    end_point, 
    lo=ride_index + 1, 
    key=lambda ride: ride[0]
)

2. Forgetting to Sort the Rides

The binary search relies on rides being sorted by start point. Forgetting this step breaks the algorithm.

Wrong:

def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
    # Missing rides.sort()!
    @cache
    def dfs(ride_index: int) -> int:
        # ... rest of the code

Correct:

def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
    rides.sort()  # Essential for binary search to work
    @cache
    def dfs(ride_index: int) -> int:
        # ... rest of the code

3. Using Wrong Search Boundary

Using i instead of i + 1 as the lower bound in binary search would include the current ride in the search range, potentially finding itself as "compatible."

Wrong:

# This could return the current ride index if end_point > start_point
next_compatible_ride = bisect_left(rides, end_point, lo=i, key=lambda x: x[0])

Correct:

# Start searching from the next ride after current
next_compatible_ride = bisect_left(rides, end_point, lo=ride_index + 1, key=lambda x: x[0])

4. Incorrect Earnings Calculation

Mixing up the earnings formula or forgetting components leads to wrong results.

Common Mistakes:

# Wrong: Forgetting the tip
take_current = dfs(next_compatible_ride) + (end_point - start_point)

# Wrong: Adding start point instead of subtracting
take_current = dfs(next_compatible_ride) + (end_point + start_point) + tip_amount

# Wrong: Using just the tip without distance
take_current = dfs(next_compatible_ride) + tip_amount

Correct:

# Earnings = distance + tip = (end - start) + tip
take_current = dfs(next_compatible_ride) + (end_point - start_point) + tip_amount

5. Cache Invalidation with Mutable Data

If rides list is modified after sorting (though unlikely in this problem), the cache would become invalid.

Prevention:

# Convert to tuple if there's any risk of modification
rides_tuple = tuple(map(tuple, rides))
# Or clear cache if rides change
dfs.cache_clear()