2008. Maximum Earnings From Taxi


Problem Description

In this problem, we are given an array called rides, which represents passengers looking for taxi rides along a road. The taxi can only move in one direction, from point 1 to point n. Each passenger request is described by three numbers: [start_i, end_i, tip_i], where start_i is the point where the passenger wants to start the ride, end_i is the point where the passenger wants to end the ride, and tip_i is the tip the passenger will give for the ride.

The revenue earned from a single passenger is equal to the distance from the start to the end of the ride plus the tip given by the passenger. The goal is to pick up the passengers in such a way as to maximize earnings. It’s important to note that a taxi driver can have only one passenger at a time in the taxi but can pick up another passenger at the same point where the last passenger was dropped off.

The question is to find out the maximum revenue that can be earned by the taxi driver by fulfilling these ride requests optimally.

Intuition

To approach this problem, an intuitive way to start thinking is through dynamic programming or recursive solutions, where we decide for each passenger whether to take them or not. What makes it challenging is that we must ensure that the choices we make are optimal at every stage.

One way to break down the problem is to sort the ride requests by their start points. This way, we can perform our decision-making process sequentially. At each step, we have two options: either pick up the current passenger or skip to the next possible ride that can be taken. If we choose to take a passenger, we must find the next ride that starts at or after our current ride ends, then calculate the earnings from the current ride plus the maximum earnings from all possible subsequent rides.

The key to implementing this solution efficiently is to use a technique called memoization, which stores the results of expensive function calls and returns the cached result when the same inputs occur again. Additionally, to avoid manually searching for the next possible ride to take after the current one ends, we can use an algorithm called binary search, which allows us to quickly find the position where the next ride starts.

By combining these techniques, we recursively explore the decision at each ride, either picking the passenger and using binary search to find our next decision point or skipping to the next passenger, and we use memoization to remember our calculated earnings to avoid redundant calculations and speed up the process. This leads to an optimized solution that can handle the given problem efficiently.

Solution Approach

The solution uses recursion and binary search along with memoization. Here's a step-by-step explanation of the implementation:

  1. Sorting the Rides: First, we sort the rides array based on the starting point of each ride. This ensures that we make decisions in the sequence of the road.

  2. Recursive Function (dfs): We define a recursive function dfs(i) that operates on the index i of the rides array. The purpose of this function is to calculate the maximum earnings starting from the i-th ride.

  3. Base Case of Recursion: The base case occurs when i is greater than or equal to the length of the rides list, indicating that there are no more rides to consider, and thus the earnings would be 0.

  4. Exploring Choices: For each ride at index i, we consider two possibilities:

    • Skip the i-th ride and move to the next one: We simply make a recursive call to dfs(i + 1).
    • Take the i-th ride: To find the next compatible ride (which starts after the current ride ends), we use a binary search to find the index j of the next ride whose start is at least as large as the end of the current ride. We then make a recursive call to dfs(j) to get the maximum earnings from rides starting at j or later. The earning of taking the i-th ride is the sum of end_i - start_i + tip_i and the earnings from the rides starting from j.
  5. Making the Optimal Choice: At each step, we must decide which choice leads to greater earnings—either skipping or taking the ride. We use the max function to determine the greater of the two earnings from the choices above.

  6. Memoization with @cache: The decorator @cache from the functools module is used on the dfs function to memoize results. This means that once we have computed the maximum earnings for a given starting index of rides, we do not have to compute it again; we can reuse the saved result. This significantly reduces the number of calculations and therefore the overall runtime of the algorithm.

  7. Binary Search: bisect_left from the bisect module is used to perform a binary search to find the next ride to consider. This search is O(log n) and is much faster than a linear search for large lists.

  8. Final Call and Answer: After defining the recursive function with all of its logic and memoization, we make the initial call to dfs(0). Because the rides array is sorted by starting point, this will consider all possible combinations starting from the first ride and return the maximum earnings possible.

Here is the key function extracted from the solution code for quick reference:

1@cache
2def dfs(i):
3    if i >= len(rides):
4        return 0
5    s, e, t = rides[i]
6    j = bisect_left(rides, e, lo=i + 1, key=lambda x: x[0])
7    return max(dfs(i + 1), dfs(j) + e - s + t)

This function is the cornerstone of our dynamic programming approach, utilizing memorization and recursion to solve the problem efficiently.

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the following rides array:

1rides = [[2, 5, 4], [3, 7, 2], [5, 9, 1], [6, 8, 6]]

Here are the steps we’ll take following the solution approach:

  1. Sorting the Rides: We sort the array rides:

    1rides.sort()  # [[2, 5, 4], [3, 7, 2], [5, 9, 1], [6, 8, 6]]
  2. Recursive Function (dfs): Define the dfs function:

    1@cache
    2def dfs(i):
    3    if i >= len(rides):
    4        return 0
    5    s, e, t = rides[i]
    6    j = bisect_left(rides, e, lo=i + 1, key=lambda x: x[0])
    7    return max(dfs(i + 1), dfs(j) + e - s + t)
  3. Base Case of Recursion: When i is out of the bounds of rides, 0 is returned.

  4. Exploring Choices: For each ride at index i, we look at two choices, skip or take the ride.

  5. Making the Optimal Choice: Use the max function to decide the best choice, which results in maximum earnings.

  6. Memoization with @cache: This ensures we do not repeat expensive calculations.

  7. Binary Search: The bisect_left function finds the next possible ride index efficiently.

  8. Final Call and Answer: We start the process by calling dfs(0).

Now, let's walk through the dfs function with this rides array:

  • We start with dfs(0). Taking the first ride [2, 5, 4], we would earn 5 - 2 + 4 = 7. We need to find the next compatible ride that starts at or after 5. Using binary search, we find that the next ride we can take is at index 2, which is [5, 9, 1].
  • We explore dfs(2) because it's the next compatible ride. If we take this ride, we'll earn 9 - 5 + 1 = 5. Now we look for the next ride after 9. No more rides can be taken, so dfs(3) will return 0. The total earning from taking rides at index 0 and 2 will be 7 + 5 = 12.
  • We now explore dfs(1) which refers to ride [3, 7, 2]. The earnings would be 7 - 3 + 2 = 6. The binary search tells us the next ride starts at index 3. If we take this ride [6, 8, 6], we earn 8 - 6 + 6 = 8. There are no more rides after this, so the total earning by taking rides at index 1 and 3 will be 6 + 8 = 14.
  • Since we want to maximize our earnings, we compare the total earnings from different sequences of rides. The maximum earning is 14 which comes from choosing rides at indices 1 and 3.

Therefore, the maximum revenue the taxi driver can earn is $14 by following the optimal path of picking up passengers from the sorted positions [3, 7, 2] and [6, 8, 6]. The implementation ensures that we are only making necessary calculations, thus optimizing our solution.

Python Solution

1from typing import List
2from functools import lru_cache
3from bisect import bisect_left
4
5class Solution:
6    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
7        # Define a memoized recursive function to compute maximum earnings
8        @lru_cache(None)  # Decorator to cache the results of the function calls
9        def dfs(index: int) -> int:
10            # Base case: when all rides have been processed
11            if index >= len(rides):
12                return 0
13              
14            # Extract the start, end and tip for the current ride
15            start, end, tip = rides[index]
16          
17            # Find the next ride that can be taken after the current ride ends
18            next_index = bisect_left(rides, end, lo=index + 1, key=lambda x: x[0])
19          
20            # Decision:
21            # 1. Skip the current ride and move to the next one: dfs(index + 1)
22            # 2. Take the current ride and then move to the next possible ride: dfs(next_index) + (end - start + tip)
23            # Choose the option that yields the maximum earnings
24            return max(dfs(index + 1), dfs(next_index) + end - start + tip)
25      
26        # Sort the rides by start time to enable binary search
27        rides.sort()
28      
29        # Start the dfs from the first ride
30        return dfs(0)
31
32# Example usage:
33# sol = Solution()
34# result = sol.maxTaxiEarnings(n, rides) # where n is the number of points in the city and rides is the list of available rides
35

Java Solution

1import java.util.Arrays;
2
3class Solution {
4    private int[][] rides; // Array to hold the information about the rides
5    private long[] memo; // Memoization array to store the maximum earnings until the ith ride
6    private int numRides; // Total number of rides
7
8    // Method to find the maximum taxi earnings
9    public long maxTaxiEarnings(int n, int[][] rides) {
10        numRides = rides.length; // Getting the number of rides
11        memo = new long[numRides]; // Initializing the memoization array
12        // Sorting rides based on their start time
13        Arrays.sort(rides, (a, b) -> a[0] - b[0]);
14        this.rides = rides; // Assigning the argument rides to class variable for use in other methods
15        return findMaxEarnings(0); // Starting the search for max earnings from the first ride
16    }
17
18    // Helper method using Depth First Search (DFS) to find the max earnings starting from ride i
19    private long findMaxEarnings(int i) {
20        if (i >= numRides) { // Base case: when no more rides are left to consider
21            return 0;
22        }
23
24        if (memo[i] != 0) { // If we have already computed this subproblem, return the stored value
25            return memo[i];
26        }
27
28        // Extract the details of the current ride
29        int start = rides[i][0], end = rides[i][1], tip = rides[i][2];
30        // Find the next ride index that can be taken after finishing the current one
31        int nextRideIndex = findNextRideIndex(end, i + 1);
32      
33        // Recursive calls to find the maximum of either taking the current ride 
34        // and the best of what follows or skipping to the next ride
35        long earningsWithCurrentRide = end - start + tip + findMaxEarnings(nextRideIndex);
36        long earningsSkippingCurrentRide = findMaxEarnings(i + 1);
37        long maxEarnings = Math.max(earningsWithCurrentRide, earningsSkippingCurrentRide);
38      
39        memo[i] = maxEarnings; // Storing the result in memoization array
40        return maxEarnings; // Returning the max earnings from current ride i onwards
41    }
42
43    // Helper method to find the next index of the ride which starts after the end time of the current ride
44    private int findNextRideIndex(int end, int startIndex) {
45        int left = startIndex, right = numRides;
46        // Binary search to find the first ride that starts after the end of the current ride
47        while (left < right) {
48            int mid = (left + right) >> 1; // Equivalent to (left + right) / 2
49            if (rides[mid][0] >= end) {
50                right = mid;
51            } else {
52                left = mid + 1;
53            }
54        }
55        return left; // Returning the index of the next ride
56    }
57}
58

C++ Solution

1using ll = long long; // Type alias for long long
2
3class Solution {
4public:
5    // Function to calculate the maximum earnings from taxi rides
6    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
7        sort(rides.begin(), rides.end()); // Sort rides based on their start times
8        int numRides = rides.size(); // Number of rides available
9        vector<ll> dp(numRides); // Dynamic programming table to store subproblem solutions
10        vector<int> nextRideStart(3); // Helper vector for binary search
11      
12        // Recursive function to find the maximum earnings starting from the i-th ride
13        function<ll(int)> findMaxEarnings = [&](int i) -> ll {
14            if (i >= numRides) return 0; // Base case: if no more rides, earnings are 0
15            if (dp[i]) return dp[i]; // If this subproblem is already solved, return the solution
16          
17            int start = rides[i][0], end = rides[i][1], tip = rides[i][2]; // Extract ride details
18            nextRideStart[0] = end; // We're looking for the next ride that starts after the current one ends
19          
20            // Find the index of the next ride to consider using binary search
21            int nextIndex = lower_bound(
22                rides.begin() + i + 1, rides.end(), nextRideStart,
23                [&](auto& left, auto& right) -> bool {
24                    return left[0] < right[0];
25                }
26            ) - rides.begin();
27          
28            // Calculate the maximum earning by either skipping the current ride or taking it
29            ll maxEarning = max(
30                findMaxEarnings(i + 1), // Skip current ride
31                findMaxEarnings(nextIndex) + end - start + tip // Take current ride
32            );
33          
34            dp[i] = maxEarning; // Store the result in the DP table
35            return maxEarning; // Return the result of the current subproblem
36        };
37      
38        // Kick off the recursion with the first ride
39        return findMaxEarnings(0);
40    }
41};
42

Typescript Solution

1type Ride = [number, number, number]; // Define Ride as a tuple of three numbers representing start, end, and tip
2
3// Create a type alias for long numbers
4type Long = number;
5
6// Function type for finding maximum earnings
7type FindMaxEarningsFunction = (i: number) => Long;
8
9// Variable for storing rides sorted by start times
10let rides: Ride[];
11
12// Dynamic programming table to store solutions of subproblems
13let dp: Long[];
14
15// Recursive function to find the maximum earnings starting from the i-th ride
16let findMaxEarnings: FindMaxEarningsFunction;
17
18/**
19 * Initialize the variables used by the findMaxEarnings function.
20 * @param ridesInput The input array of rides.
21 */
22function initialize(ridesInput: Ride[]): void {
23  // Initialize the rides array and sort it based on their start times
24  rides = ridesInput.sort((a, b) => a[0] - b[0]);
25
26  // Initialize the dp array with zeros
27  dp = new Array(rides.length).fill(0);
28
29  // Define the recursive function to find the maximum earnings
30  findMaxEarnings = (i: number): Long => {
31    if (i >= rides.length) return 0; // Base case: No more rides, earnings are 0
32    if (dp[i]) return dp[i]; // If the subproblem is already solved, return the cached result
33  
34    const [start, end, tip] = rides[i]; // Extract ride details
35    // Look for the next ride that starts after the current one ends
36    let nextRideStart = end;
37  
38    // Find the index of the next ride to consider using binary search
39    const nextIndex = binarySearchNextIndex(rides, i + 1, nextRideStart);
40  
41    // Calculate the maximum earnings by either skipping the current ride or taking it
42    const maxEarning = Math.max(
43      findMaxEarnings(i + 1), // Skip current ride
44      findMaxEarnings(nextIndex) + end - start + tip // Take current ride
45    );
46  
47    dp[i] = maxEarning; // Store the result in the DP table
48    return maxEarning; // Return the result for the current subproblem
49  };
50}
51
52/**
53 * Binary search to find the index of the first ride that starts after a certain time.
54 * @param rides The list of rides.
55 * @param startIdx The start index for the search.
56 * @param nextRideStartTime The earliest start time for the next ride.
57 */
58function binarySearchNextIndex(rides: Ride[], startIdx: number, nextRideStartTime: number): number {
59  let low = startIdx;
60  let high = rides.length;
61
62  while (low < high) {
63    const mid = Math.floor((low + high) / 2);
64    if (rides[mid][0] < nextRideStartTime) {
65      low = mid + 1;
66    } else {
67      high = mid;
68    }
69  }
70
71  return low;
72}
73
74/**
75 * Calculate the maximum earnings from taxi rides.
76 * @param n The number of points (ignored as it's not used after sorting rides).
77 * @param ridesInput The input array of rides.
78 * @returns The maximum earnings from the rides.
79 */
80function maxTaxiEarnings(n: number, ridesInput: Ride[]): Long {
81  // Initialize necessary data structures and functions
82  initialize(ridesInput);
83  // Kick off the recursion with the first ride
84  return findMaxEarnings(0);
85}
86
87// Example usage:
88const n = 5;
89const rideList: Ride[] = [[2, 5, 4], [1, 5, 1]];
90console.log(maxTaxiEarnings(n, rideList)); // Output the maximum earnings from given taxi rides
91

Time and Space Complexity

The given Python code represents a solution to a problem related to taxi earnings, where an input list rides consists of rides information, and each ride includes a start time, an end time, and a tip. The solution computes the maximum earnings possible by following a specific strategy using dynamic programming and binary search.

Let's analyze the time complexity and space complexity of the code:

Time Complexity:

  1. Sorting the Rides: The initial step in the code is to sort the rides list, which consists of m ride intervals. This has a time complexity of O(m log m), where m is the number of rides.

  2. Dynamic Programming with Memoization (dfs function): The dfs function is used here to implement dynamic programming with memoization. The memoization ensures that each possible starting point of a ride is computed at most once. Since memoization caches the results, the maximum number of distinct states to consider is m, the length of the sorted rides list.

  3. Binary Search (bisect_left function): Inside the dfs function, binary search is used to find the next non-overlapping ride, which has a time complexity of O(log m) per call.

Combining the dynamic programming computation with the binary search, for each of the m calls to dfs, a binary search operation is involved. Thus, each call may contribute up to O(log m) complexity. Given that there are m such calls, the total time complexity from the dynamic programming along with the binary searches is O(m log m).

Considering both sorting and the memoized dfs, the overall time complexity of the algorithm is O(m log m).

Space Complexity:

  1. Sorting: Sorting is done in-place in Python (Timsort), but it may still require O(log m) space for the stack frames used in the sort implementation.

  2. Memoization: The dfs function uses a memoization table (implicitly through the @cache decorator), which will store results for each unique argument (i). This could result in up to m entries in the worst case, giving a space complexity of O(m).

  3. Recursion Stack: The depth of recursion may go up to m in the worst case if all rides are taken sequentially with no overlap, which contributes to O(m) space complexity.

Thus, combining the space requirements for the sorting, memoization, and recursion stack, the total space complexity is O(m).

In conclusion, the time complexity of the code is O(m log m) and the space complexity is O(m), where m is the number of rides.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫