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] = [starti, endi, tipi] denotes the ith passenger requesting a ride from point starti to point endi who is willing to give a tipi dollar tip.
For each passenger i you pick up, you earn endi - starti + tipi 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 <= 1051 <= rides.length <= 3 * 104rides[i].length == 31 <= starti < endi <= n1 <= tipi <= 105Problem Overview: You drive a taxi on a road with locations from 1 to n. Each ride has a start point, end point, and tip. When you accept a ride you must complete it before starting another. The task is to select a set of non‑overlapping rides that maximizes total earnings (end - start + tip).
Approach 1: Quadratic Dynamic Programming (O(m²) time, O(m) space)
Sort all rides by their end position using sorting. Define dp[i] as the maximum profit considering rides up to index i. For each ride i, compute its earnings and check every previous ride j. If rides[j].end <= rides[i].start, the two rides are compatible and you can combine their profits. Update dp[i] = max(dp[i], dp[j] + profit_i). This approach clearly models the weighted interval scheduling idea but becomes slow because every ride scans all previous rides.
Approach 2: Dynamic Programming with Binary Search (O(m log m) time, O(m) space)
After sorting rides by end location, maintain a DP array where dp[i] stores the maximum earnings using the first i rides. For each ride, compute its profit and use binary search to find the last ride whose end point is <= start. This gives the best compatible ride in O(log m). The transition becomes dp[i] = max(dp[i-1], dp[prev] + profit). The key insight: because rides are sorted by end time, compatible rides form a prefix, so binary search replaces the quadratic scan.
Approach 3: Greedy + Dynamic Programming Optimization (O(n + m log m) time, O(n) space)
Instead of indexing DP by rides, index it by road position. Create a map from start position to rides beginning there using an array or adjacency list. Iterate positions from 1 to n and carry forward the best earnings so far: dp[i] = max(dp[i], dp[i-1]). For every ride starting at i, update dp[end] = max(dp[end], dp[i] + end - start + tip). This acts like a greedy sweep along the road while still relying on dynamic programming. It avoids searching previous rides and works well when n is manageable.
Recommended for interviews: Dynamic Programming with Binary Search is the expected solution. It shows you recognize the weighted interval scheduling pattern and know how to optimize the compatibility check with binary search. Starting with the quadratic DP demonstrates understanding of the state transition, but the optimized O(m log m) approach shows strong algorithmic reasoning.
In this approach, we utilize dynamic programming along with binary search to maximize earnings. The idea is to process rides in order of their end points. For each ride, we use binary search to efficiently find the maximum profit we can accumulate until the start point of the current ride. This helps in deciding if we should pick up the current ride to maximize profits.
We maintain a 'dp' array where 'dp[i]' stores the maximum profit that can be earned by considering rides up to point 'i'. We iterate through each ride, check if taking this ride improves the overall profit compared to not taking it, using the `dp` value at the ride's start point. We use binary search to quickly find the previous rides that end before the current ride starts.
This solution leverages dynamic programming to calculate the maximum fundable earnings route. We transform the problem into a decision-making process of whether to take the next ride by adding to previous maximum earnings at the start point or not. Sorting rides based on their end point enables efficient use of binary search to determine past contributing segments.
Time Complexity: O(m log m) where m is the number of rides. Sorting takes O(m log m) and for each ride, binary search might take O(m log m) in the worst case.
Space Complexity: O(m) for the dp array.
This approach fuses a priority queue (or heap) with dynamic programming to select optimal rides greedily based on profit potential. We utilize a max heap to track ongoing ride profits and dynamically update potential maximums as the rides process. The goal is to rapidly determine and add the best potential future profits.
In this strategy, rides are evaluated over possible earnings, allowing the priority mechanism to determine profitable pickups optimally faster.
This Python solution embraces a heuristic approach combining greedy ride picking strategies via a priority queue, and updating potential revenues efficiently. Sorting rides and managing a dynamic records heap permits optimal profit accumulation for solving the specified task efficiently.
Python
JavaScript
Time Complexity: O(m log m), as sort and heap operations predominantly dictate performance times.
Space Complexity: O(m), considering the heap and storage elements.
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).
The calculation process of the function dfs(i) is as follows:
For the i-th passenger, we can choose to accept or not to accept the order. If we don't accept the order, the maximum tip that can be obtained is dfs(i + 1). If we accept the order, we can use binary search to find the first passenger encountered after the drop-off point of the i-th passenger, denoted as j. The maximum tip that can be obtained is dfs(j) + end_i - start_i + tip_i. Take the larger of the two. That is:
$
dfs(i) = max(dfs(i + 1), dfs(j) + end_i - start_i + tip_i)
Where j is the smallest index that satisfies start_j \ge end_i, which can be obtained by binary search.
In this process, we can use memoization search to save the answer of each state to avoid repeated calculations.
The time complexity is O(m times log m), and the space complexity is O(m). Here, m is the length of rides$.
Python
Java
C++
Go
TypeScript
We can change the memoization search in Solution 1 to dynamic programming.
First, sort rides, this time we sort by end in ascending order. Then define f[i], which represents the maximum tip that can be obtained from the first i passengers. Initially, f[0] = 0, and the answer is f[m].
For the i-th passenger, we can choose to accept or not to accept the order. If we don't accept the order, the maximum tip that can be obtained is f[i-1]. If we accept the order, we can use binary search to find the last passenger whose drop-off point is not greater than start_i before the i-th passenger gets on the car, denoted as j. The maximum tip that can be obtained is f[j] + end_i - start_i + tip_i. Take the larger of the two. That is:
$
f[i] = max(f[i - 1], f[j] + end_i - start_i + tip_i)
Where j is the largest index that satisfies end_j \le start_i, which can be obtained by binary search.
The time complexity is O(m times log m), and the space complexity is O(m). Here, m is the length of rides$.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Binary Search | Time Complexity: O(m log m) where m is the number of rides. Sorting takes O(m log m) and for each ride, binary search might take O(m log m) in the worst case. |
| Greedy + Dynamic Programming Optimization Strategy | Time Complexity: O(m log m), as sort and heap operations predominantly dictate performance times. |
| Memoization Search + Binary Search | — |
| Dynamic Programming + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Quadratic Dynamic Programming | O(m²) | O(m) | Conceptual baseline to understand weighted interval scheduling |
| DP with Binary Search | O(m log m) | O(m) | General optimal solution when rides are treated as intervals |
| Greedy Sweep + DP by Position | O(n + m log m) | O(n) | Efficient when iterating along road positions and grouping rides by start |
LeetCode 2008. Maximum Earnings From Taxi • Happy Coding • 6,224 views views
Watch 9 more video solutions →Practice Maximum Earnings From Taxi with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor