Maximum Earnings From Taxi

Medium

Uber

24 views

Topics:

ArraysDynamic ProgrammingBinary Search

There are n points on a road you are driving your taxi on. The n points on the road are labeled from 1 to n in the direction you are going, and you want to drive from point 1 to point n to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a 0-indexed 2D integer array rides, where rides[i] = [start_i, end_i, tip_i] denotes the i^th passenger requesting a ride from point start_i to point end_i who is willing to give a tip_i dollar tip.

For each passenger i you pick up, you earn end_i - start_i + tip_i dollars. You may only drive at most one passenger at a time.

Given n and rides, return the maximum number of dollars you can earn by picking up the passengers optimally.

Note: You may drop off a passenger and pick up a different passenger at the same point.

Example 1:

Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7
Explanation: We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

Example 2:

Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20
Explanation: We will pick up the following passengers:
- Drive passenger 1 from point 3 to point 10 for a profit of 10 - 3 + 2 = 9 dollars.
- Drive passenger 2 from point 10 to point 12 for a profit of 12 - 10 + 3 = 5 dollars.
- Drive passenger 5 from point 13 to point 18 for a profit of 18 - 13 + 1 = 6 dollars.
We earn 9 + 5 + 6 = 20 dollars in total.

Constraints:

1 <= n <= 10⁵
1 <= rides.length <= 3 * 10⁴
rides[i].length == 3
1 <= start_i < end_i <= n
1 <= tip_i <= 10⁵

Maximum Earnings From Taxi

Medium

Uber

24 views

Topics:

ArraysDynamic ProgrammingBinary Search

There are n points on a road you are driving your taxi on. The n points on the road are labeled from 1 to n in the direction you are going, and you want to drive from point 1 to point n to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a 0-indexed 2D integer array rides, where rides[i] = [start_i, end_i, tip_i] denotes the i^th passenger requesting a ride from point start_i to point end_i who is willing to give a tip_i dollar tip.

For each passenger i you pick up, you earn end_i - start_i + tip_i dollars. You may only drive at most one passenger at a time.

Given n and rides, return the maximum number of dollars you can earn by picking up the passengers optimally.

Note: You may drop off a passenger and pick up a different passenger at the same point.

Example 1:

Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7
Explanation: We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

Example 2:

Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20
Explanation: We will pick up the following passengers:
- Drive passenger 1 from point 3 to point 10 for a profit of 10 - 3 + 2 = 9 dollars.
- Drive passenger 2 from point 10 to point 12 for a profit of 12 - 10 + 3 = 5 dollars.
- Drive passenger 5 from point 13 to point 18 for a profit of 18 - 13 + 1 = 6 dollars.
We earn 9 + 5 + 6 = 20 dollars in total.

Constraints:

1 <= n <= 10⁵
1 <= rides.length <= 3 * 10⁴
rides[i].length == 3
1 <= start_i < end_i <= n
1 <= tip_i <= 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper bounds for 'n', the start location, the end location, and the tip?
Can the start location ever be equal to the end location for a ride? If so, what is the expected earnings?
If no rides can be taken (e.g., no compatible schedules), what value should I return?
Are the rides sorted in any particular order, such as by start time, end time, or tip amount? If not, can I assume they are unsorted?
Are the start and end locations guaranteed to be within the range [1, n] inclusive?

Brute Force Solution

Approach

The core idea is to explore all possible combinations of taxi ride choices to find the most profitable one. We will look at every possible subset of rides. Then, we'll calculate the earnings for each valid subset and pick the subset that provides maximum earnings.

Here's how the algorithm would work step-by-step:

Consider each possible combination of rides - one ride alone, two rides together, three rides together, and so on, all the way up to using every single ride.
For each combination of rides you look at, check if it is a valid combination. A valid combination means that no two rides overlap in terms of start and end locations. A taxi can only do one trip at a time.
If a combination is valid, calculate the total earnings you would get from taking those rides.
Compare the earnings of all the valid combinations and find the one that gives you the highest total earnings. That's your answer.

Code Implementation

def max_taxi_earnings_brute_force(number_of_locations, rides):
    max_earnings = 0
    number_of_rides = len(rides)

    # Iterate through all possible subsets of rides
    for i in range(1 << number_of_rides):
        current_rides = []

        # Select the rides for the current subset
        for j in range(number_of_rides):
            if (i >> j) & 1:
                current_rides.append(rides[j])

        is_valid = True

        # Check if the selected rides are non-overlapping.
        for first_ride_index in range(len(current_rides)):
            for second_ride_index in range(first_ride_index + 1, len(current_rides)):
                start_first, end_first, _ = current_rides[first_ride_index]
                start_second, end_second, _ = current_rides[second_ride_index]

                #Overlapping rides are invalid
                if not (end_first <= start_second or end_second <= start_first):
                    is_valid = False
                    break

            if not is_valid:
                break

        #Calculate profit only if valid
        if is_valid:
            current_earnings = 0

            # Sum up the earnings for current valid rides
            for ride in current_rides:
                start_location, end_location, tip = ride
                current_earnings += (end_location - start_location + tip)

            # Store the max earning from valid rides
            max_earnings = max(max_earnings, current_earnings)

    return max_earnings

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n * n * log(n)) – The algorithm considers all possible subsets of rides, leading to 2^n combinations. For each subset, it checks for overlapping rides, which can take O(n * log(n)) time. Checking for overlaps involves sorting the rides by start time and then checking if the end time of a ride is before the start time of the next ride, resulting in O(n log n) time. Therefore, the total time complexity is approximately O(2^n * n * log(n)).

Space Complexity

O(1) – The provided plain English explanation describes iterating through combinations and checking their validity. It doesn't mention the creation of any auxiliary data structures that scale with the input size N (number of rides). No temporary lists, hash maps, or significant recursion are implied by the description. Thus, the algorithm seems to operate in constant auxiliary space, using only a few variables to track indices or intermediate calculations.

Optimal Solution

Approach

The optimal strategy for maximizing taxi earnings involves using a technique that builds the best solution step by step, avoiding re-calculations. We aim to find the most profitable route to each possible destination by remembering the best results we've seen so far.

Here's how the algorithm would work step-by-step:

Imagine each location where a passenger can get in or out of your taxi is a stop on a route.
Start at the beginning location (location 1) and consider all possible trips you can take from there.
For each trip, calculate the earnings you would make, and add that to the best earnings you could have had *before* that trip.
Keep track of the best possible earnings you can have at each location. If there are multiple ways to get to the same location, remember only the one that gives you the highest earnings.
Continue moving from location to location, always checking the possible trips and updating the best earnings for each location based on the highest possible profit.
When you reach the final location, the best earnings you have stored for that location is the maximum earnings you can achieve.

Code Implementation

def max_taxi_earnings(number_of_stops, rides):
    maximum_earnings_at_stop = [0] * (number_of_stops + 1)

    rides.sort()

    for start_position, end_position, tip_amount in rides:
        # Determine profit for the current ride.
        ride_profit = end_position - start_position + tip_amount

        # See if taking the current ride leads to more profit.
        potential_earnings = maximum_earnings_at_stop[start_position] + ride_profit

        # Keep the maximum earnings seen so far.
        maximum_earnings_at_stop[end_position] = max(maximum_earnings_at_stop[end_position], potential_earnings)

        for i in range(end_position + 1, number_of_stops + 1):
            maximum_earnings_at_stop[i] = max(maximum_earnings_at_stop[i], maximum_earnings_at_stop[end_position])

    return maximum_earnings_at_stop[number_of_stops]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n + m log m) – The algorithm involves sorting the rides based on their end locations, which takes O(m log m) time, where m is the number of rides. Subsequently, we iterate through all possible locations from 1 to n (where n is the final location), which contributes O(n) to the time complexity. Within each location, we potentially iterate through the rides that end at that location. However, since the sorting step dominates the time, the overall time complexity is O(n + m log m).

Space Complexity

O(N) – The algorithm keeps track of the best possible earnings at each location, which can be represented as an array (or map) where the index corresponds to the location. Since the locations range from 1 to the final location (N), we need to store earnings for each location up to N. Therefore, the auxiliary space used is proportional to N. This means we have an array, or similar data structure, of size N storing the maximum earnings up to each location, contributing to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty rides array	Return 0 as no rides mean no earnings.
n = 1 and rides exist, but only start/end at location 1	The solution should still process valid rides even if n is small, returning the tip of the ride.
Rides array with one ride	The maximum earnings are simply the tip of that single ride.
Rides array with multiple rides that are mutually exclusive (non-overlapping)	The solution should sum the tips of all the non-overlapping rides.
Rides array with multiple rides that are all overlapping	The solution must choose the ride with the maximum tip from the overlapping set.
Large n and a large number of rides, potentially leading to performance issues	Use dynamic programming with memoization or bottom-up iteration for optimal performance, avoiding recursion's potential stack overflow.
Rides with zero tip	Rides with zero tip should still be considered when determining the optimal schedule since they can enable selection of other high-tip rides.
Rides where start equals end	The solution should treat these rides as invalid and exclude them from the calculation as they consume no time but might incorrectly inflate potential earnings.