#2008

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Earnings From Taxi

Maximize earnings by optimizing taxi ride selection and tips using array scanning, hash lookups, and sorting.

array hash table binary search dynamic programming sorting

Problem Statement

You're driving a taxi from point 1 to point n, and you aim to maximize your earnings by picking up passengers along the way. The road is divided into n points, and each passenger is represented by a ride described by their starting point, ending point, and tip. Your goal is to find the maximum possible earnings by selecting passengers whose rides do not overlap, and each ride's profit depends on the difference between the end and start points, plus the tip offered.

You can only pick up one passenger at a time, and once you pick a passenger, you must drive them directly to their destination without detouring. The task is to determine the maximum earnings achievable by carefully selecting which passengers to pick up, ensuring you maximize the route profit without breaking the rule of only one passenger per trip.

Examples

Example 1

Input: n = 5, rides = [[2,5,4],[1,5,1]]

Output: 7

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

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 <= 105
1 <= rides.length <= 3 * 104
rides[i].length == 3
1 <= starti < endi <= n
1 <= tipi <= 105

Solution Approach

Sorting Rides by End Point

Sort the rides array by the ending point of each passenger's ride. This allows you to efficiently determine the maximum possible earnings while considering which previous rides may overlap with the current one.

Dynamic Programming with Hash Table Lookup

Use a dynamic programming approach where you maintain an array or hash table of maximum earnings at each point. As you iterate through sorted rides, use a hash lookup to find the maximum earnings up to the starting point of each passenger's ride.

Greedy Selection of Non-Overlapping Rides

Implement a greedy approach to select the maximum profit from each passenger while ensuring that the rides do not overlap. This involves comparing the current ride's starting point with the previously selected ride's ending point and making optimal decisions at each step.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on sorting the rides and performing efficient lookups or dynamic programming updates. Sorting takes O(m log m), where m is the number of rides, and the dynamic programming step is O(m). The overall complexity is O(m log m), where m is the number of rides.

What Interviewers Usually Probe

Understanding dynamic programming and hash table usage for optimized solutions.
Ability to identify and implement efficient algorithms for overlapping interval problems.
Proficiency with greedy algorithms for selecting non-overlapping tasks.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check for ride overlap or choosing an incorrect ride combination.
Not optimizing the solution by sorting rides before applying dynamic programming.
Misunderstanding the interaction between dynamic programming and hash table lookups.

Follow-up variants

Increased number of rides to test performance optimization.
Introducing additional constraints on maximum ride length or tips.
Allowing multiple passengers at a time to drive, increasing complexity.

FAQ

What is the primary approach for solving the Maximum Earnings From Taxi problem?

The problem can be solved using a combination of sorting, dynamic programming, and hash table lookups to efficiently track maximum earnings.

How does dynamic programming help in this problem?

Dynamic programming is used to keep track of the maximum earnings at each point, considering the rides picked up and ensuring that they don't overlap.

Can sorting the rides by their ending points improve the solution?

Yes, sorting the rides by their ending points allows for efficient comparison and helps avoid overlapping rides while optimizing earnings.

Why is hash table lookup important in this problem?

Hash table lookup helps in quickly retrieving the maximum earnings up to a specific point in the ride sequence, enabling efficient dynamic programming.

What are the potential variants of the Maximum Earnings From Taxi problem?

Variants include handling a larger number of rides, imposing additional constraints on ride lengths or tips, or allowing multiple passengers per trip.

terminal

Solution

Solution 1: Memoization Search + Binary Search

First, we sort $rides$ in ascending order by $start$. Then we design a function $dfs(i)$, which represents the maximum tip that can be obtained from accepting orders starting from the $i$-th passenger. The answer is $dfs(0)$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(rides):
                return 0
            st, ed, tip = rides[i]
            j = bisect_left(rides, ed, lo=i + 1, key=lambda x: x[0])
            return max(dfs(i + 1), dfs(j) + ed - st + tip)

        rides.sort()
        return dfs(0)

Solution 2: Dynamic Programming + Binary Search

We can change the memoization search in Solution 1 to dynamic programming.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(rides):
                return 0
            st, ed, tip = rides[i]
            j = bisect_left(rides, ed, lo=i + 1, key=lambda x: x[0])
            return max(dfs(i + 1), dfs(j) + ed - st + tip)

        rides.sort()
        return dfs(0)

Continue Practicing

#2501 longest square streak in an array #2713 maximum strictly increasing cells in a matrix #2830 maximize the profit as the salesman