We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Earnings From Taxi

Difficulty: Medium

Problem Description

Given n points on a road and a 2D integer array rides, where each ride consists of a starting point, an ending point, and a tip, determine the maximum earnings possible by optimally picking up passengers while driving from point 1 to point n. You can only drive one passenger at a time and may drop off a passenger and pick up a different one at the same point.

Key Insights

  • Earnings from a ride can be calculated as end_i - start_i + tip_i.
  • Passengers can only be picked up in the order they are encountered on the road.
  • Dynamic programming can be used to keep track of the maximum earnings up to each point on the road.
  • Efficiently manage overlapping rides to maximize total earnings.

Space and Time Complexity

Time Complexity: O(m log m + n), where m is the number of rides (due to sorting) and n is the number of points on the road. Space Complexity: O(n) for the dynamic programming array.

Solution

To solve this problem, we can use a dynamic programming approach combined with sorting and binary search. We will:

  1. Calculate the earnings for each ride.
  2. Sort the rides based on their ending points.
  3. Use a dynamic programming array to track the maximum earnings at each point on the road.
  4. For each ride, determine the optimal point to drop off the previous passenger and pick up the current passenger using binary search.

Code Solutions

def maxEarnings(n, rides):
    # Step 1: Calculate earnings for each ride and store them in a list
    earnings = []
    for start, end, tip in rides:
        earnings.append((start, end, end - start + tip))
    
    # Step 2: Sort the rides based on their ending point
    earnings.sort(key=lambda x: x[1])
    
    # Step 3: Dynamic programming array to store max earnings up to each point
    dp = [0] * (n + 1)
    index = 0
    m = len(earnings)
    
    for i in range(1, n + 1):
        # Carry forward the previous maximum earnings
        dp[i] = dp[i - 1]
        
        # Check for any rides that end at this point
        while index < m and earnings[index][1] == i:
            start = earnings[index][0]
            ride_earnings = earnings[index][2]
            # Update dp[i] with the best possible earnings if we take this ride
            dp[i] = max(dp[i], dp[start - 1] + ride_earnings)
            index += 1
            
    return dp[n]
← Back to All Questions