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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Earnings From Taxi

Number: 2118

Difficulty: Medium

Paid? No

Companies: Salesforce, Uber, Myntra

Problem Description

You are given n points along a road (numbered 1 through n) where you drive a taxi. There are multiple rides, each represented by [start, end, tip]. Picking a ride from point start to end earns you (end - start + tip) dollars. You cannot drive backward and you can only take one ride at a time. However, you can drop off a passenger and then immediately pick up another ride from the drop-off point. The goal is to determine the maximum total earnings possible by picking rides optimally.

Key Insights

  • Sort the rides based on the starting point to process them in order.
  • Use dynamic programming (DP) to determine the maximum earnings starting from each ride.
  • Use binary search to find the next ride that you can take after finishing the current ride, thus ensuring non-overlapping rides.
  • The state transition for DP is based on:
    • Skipping the current ride.
    • Taking the current ride, earning its profit (calculated as end - start + tip) and then adding the best profit obtainable from rides starting at or after the current ride’s end.
  • This challenge is similar to weighted interval scheduling.

Space and Time Complexity

Time Complexity: O(m log m) where m is the number of rides (due to sorting and binary search for each ride).
Space Complexity: O(m) for storing the DP array and auxiliary arrays for binary search.

Solution

The solution uses dynamic programming coupled with binary search. First, we sort the rides by their start time. Then, we define a DP array where DP[i] represents the maximum earnings possible starting from the i-th ride in the sorted order. We iterate backwards over the rides. For each ride, we calculate the earnings from taking that ride (end - start + tip) and look up (via binary search) the index of the next ride that starts at or after the current ride’s end. The DP recurrence is:

 DP[i] = max( DP[i+1] (skipping the ride), rideProfit + DP[nextRideIndex] (taking the ride) )

Finally, DP[0] will give us the answer. The approach cleverly combines sorting and binary search to efficiently chain rides without overlap.

Code Solutions

# Python solution with detailed comments
def maxTaxiEarnings(n, rides):
    # Step 1: Sort the rides based on their starting point
    rides.sort(key=lambda ride: ride[0])
    m = len(rides)
    
    # Create an array for DP where dp[i] is max earnings from rides[i:]
    dp = [0] * (m + 1)
    
    # Gather all starting times to use for binary search
    start_times = [ride[0] for ride in rides]
    
    # Iterate from the last ride backwards
    for i in range(m - 1, -1, -1):
        start, end, tip = rides[i]
        # Calculate profit from taking this ride
        current_profit = end - start + tip
        
        # Use binary search to find the next ride whose start is >= current ride's end
        left, right = i + 1, m
        while left < right:
            mid = (left + right) // 2
            if rides[mid][0] >= end:
                right = mid
            else:
                left = mid + 1
        next_index = left
        
        # Option1: Take the ride and add profit from next available ride found using binary search
        take_ride = current_profit + dp[next_index]
        # Option2: Skip the current ride and take best from next ride
        skip_ride = dp[i + 1]
        # Choose the maximum of taking or skipping the ride
        dp[i] = max(take_ride, skip_ride)
    
    # The answer is stored at dp[0] which represents maximum earnings from all rides
    return dp[0]

# Example usage:
n = 5
rides = [[2,5,4], [1,5,1]]
print(maxTaxiEarnings(n, rides))  # Expected output: 7
← Back to All Questions