Maximum Earnings From Taxi - Leetcode Solution

The "Maximum Earnings From Taxi" problem on LeetCode is a dynamic programming problem that requires finding the maximum earnings a taxi driver can make by taking rides from a list of given rides that are sorted by their start time. The driver can take rides starting from any time, but cannot take more than one ride at a time.

Here's a detailed solution for the problem:

Approach:

• Sort the rides according to their start time.
• Initialize a list of earnings with length equals to the end time of the last ride. This list will hold the maximum earnings that can be made up to a given time.
• Iterate through the rides, for each ride, find the maximum earnings that can be made by either taking the ride or not. Add the ride earnings to the maximum of those two options and store it at the end time of the ride.
• Finally, the maximum earning to be made up to the end time of the last ride is returned.

Algorithm:

1. Sort the rides according to their start time.
2. Create a list of earnings with length equals to the end time of the last ride.
3. Initialize the first earning to be 0.
4. Iterate through the rides, for each ride:
   • Find the maximum of two options:
     • Earnings made by not taking the ride, which is the earnings up to the start time of the ride.
     • Earnings made by taking the ride, which is the earnings up to the start time of the ride plus the ride earnings.
   • Store the maximum earning at the end time of the ride.
5. Return the maximum earning up to the end time of the last ride.

Code:

def maxTaxiEarnings(n: int, rides: List[List[int]]) -> int: rides.sort(key=lambda x: x[0]) earnings = [0] * (rides[-1][1] + 1)

for start, end, tip in rides:
    curr_earnings = max(earnings[end], earnings[start] + tip)
    earnings[end] = max(earnings[end], curr_earnings)

return earnings[-1]

Explanation of the Code:

• The function takes in two arguments, 'n' which is the number of rides, and 'rides', which is a list of rides.
• The 'rides' list is sorted according to their start time using the 'sort' function and the lambda function.
• The 'earnings' list is initialized with length equals to the end time of the last ride as all rides must end by this time.
• The first element of the 'earnings' list is set to '0' as no earnings are made before the first ride.
• An iteration through the rides is initiated, for each ride:
  • The maximum of two options is computed:
    • The earnings made by not taking the ride, which is the maximum earnings up to the start time of the ride.
    • The earnings made by taking the ride, which is the maximum earnings up to the start time of the ride plus the tip earned from taking the ride.
  • The maximum earning is stored at the end time of the ride.
• The maximum earnings up to the end time of the last ride is returned.

Runtime Complexity: O(n log n) for sorting the rides, and O(n) for the iteration.

Space Complexity: O(max_end_time) for the 'earnings' list.

Overall, the solution is optimal as it runs in O(n log n + max_end_time) time and O(max_end_time) space.

1