Watch 10 video solutions for Maximum Earnings From Taxi, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by Happy Coding has 6,224 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |