Maximum Earnings From Taxi
Maximum Earnings From Taxi is a medium dynamic programming problem solved with the 1d dp pattern.
The best approach, optimal (dp over road points), runs in O(n + m) time and O(n + m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dp over rides, scan all earlier rides) up.
Problem
A taxi drives along a one-way road with points labelled 1 to n, always moving from lower to higher labels. Ride requests are given as rides[i] = [start_i, end_i, tip_i]: a passenger wants to go from start_i to end_i and will tip tip_i.
Taking ride i earns end_i - start_i + tip_i. The taxi carries at most one passenger at a time, but it may pick someone up at the same point where it drops someone off. Starting at point 1, return the maximum total the driver can earn by choosing which rides to accept.
Examples
Example 1
- Input
n = 8, rides = [[1, 4, 2], [3, 7, 1], [4, 8, 0], [2, 3, 6]]- Output
12- Why
- Ride [2, 3, 6] earns 1 + 6 = 7 and ride [3, 7, 1] earns 4 + 1 = 5. They meet at point 3, so both can be taken.
Example 2
- Input
n = 5, rides = [[1, 5, 0]]- Output
4- Why
- The only ride earns 5 - 1 + 0 = 4.
Constraints
1 <= n <= 10^51 <= rides.length <= 3 * 10^4rides[i] = [start_i, end_i, tip_i]with1 <= start_i < end_i <= nand0 <= tip_i <= 10^5
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (DP over rides, scan all earlier rides) | O(m²) | O(m) |
| Optimal (DP over road points) | O(n + m) | O(n + m) |
1Brute force (DP over rides, scan all earlier rides)
O(m²)Each of the m rides scans every earlier ride.O(m)One dp value per ride.Sort rides by end. dp[i] is the best total over the first i + 1 rides where ride i is the last one taken. It equals the ride's own earning plus the best dp[j] among earlier rides that end at or before ride i starts. The answer is the largest dp value.
- Sort rides by end point.
- For each ride i:
dp[i] = end - start + tip; for each j < i withend_j <= start_i,dp[i] = max(dp[i], dp[j] + earn_i). - Return the maximum dp value.
class Solution {
public long maxTaxiEarnings(int n, int[][] rides) {
int m = rides.length;
int[][] r = rides.clone();
Arrays.sort(r, (a, b) -> Integer.compare(a[1], b[1]));
long[] dp = new long[m];
long best = 0;
for (int i = 0; i < m; i++) {
long earn = r[i][1] - r[i][0] + r[i][2];
dp[i] = earn;
for (int j = 0; j < i; j++)
if (r[j][1] <= r[i][0]) dp[i] = Math.max(dp[i], dp[j] + earn);
best = Math.max(best, dp[i]);
}
return best;
}
}class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
r = sorted(rides, key=lambda x: x[1])
m = len(r)
dp = [0] * m
best = 0
for i in range(m):
earn = r[i][1] - r[i][0] + r[i][2]
dp[i] = earn
for j in range(i):
if r[j][1] <= r[i][0]:
dp[i] = max(dp[i], dp[j] + earn)
best = max(best, dp[i])
return bestclass Solution {
public:
long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
vector<vector<int>> r(rides.begin(), rides.end());
sort(r.begin(), r.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
int m = r.size();
vector<long long> dp(m);
long long best = 0;
for (int i = 0; i < m; i++) {
long long earn = (long long)r[i][1] - r[i][0] + r[i][2];
dp[i] = earn;
for (int j = 0; j < i; j++)
if (r[j][1] <= r[i][0]) dp[i] = max(dp[i], dp[j] + earn);
best = max(best, dp[i]);
}
return best;
}
};function maxTaxiEarnings(n, rides) {
const r = [...rides].sort((a, b) => a[1] - b[1]);
const m = r.length;
const dp = new Array(m).fill(0);
let best = 0;
for (let i = 0; i < m; i++) {
const earn = r[i][1] - r[i][0] + r[i][2];
dp[i] = earn;
for (let j = 0; j < i; j++)
if (r[j][1] <= r[i][0]) dp[i] = Math.max(dp[i], dp[j] + earn);
best = Math.max(best, dp[i]);
}
return best;
}2Optimal (DP over road points)
O(n + m)Each point is visited once and each ride is checked once at its end point.O(n + m)The best array of size n + 1 and the buckets holding m rides.Let best[x] be the most you can have earned when the car reaches point x. Arriving at x without finishing a ride there keeps best[x - 1]; finishing ride [s, x, t] gives best[s] + (x - s + t). Bucket the rides by their end point so every point checks only its own rides. The answer is best[n].
- Build lists
endsAt[x]holding the rides that end at x. best[1] = 0. For x from 2 to n:best[x] = best[x - 1].- For each ride [s, x, t] in
endsAt[x]:best[x] = max(best[x], best[s] + x - s + t). - Return
best[n].
class Solution {
public long maxTaxiEarnings(int n, int[][] rides) {
List<List<int[]>> endsAt = new ArrayList<>();
for (int i = 0; i <= n; i++) endsAt.add(new ArrayList<>());
for (int[] r : rides) endsAt.get(r[1]).add(r);
long[] best = new long[n + 1];
for (int x = 2; x <= n; x++) {
best[x] = best[x - 1];
for (int[] r : endsAt.get(x))
best[x] = Math.max(best[x], best[r[0]] + x - r[0] + r[2]);
}
return best[n];
}
}class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
ends_at = [[] for _ in range(n + 1)]
for s, e, t in rides:
ends_at[e].append((s, t))
best = [0] * (n + 1)
for x in range(2, n + 1):
b = best[x - 1]
for s, t in ends_at[x]:
cand = best[s] + x - s + t
if cand > b:
b = cand
best[x] = b
return best[n]class Solution {
public:
long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
vector<vector<pair<int, int>>> endsAt(n + 1);
for (auto& r : rides) endsAt[r[1]].push_back({r[0], r[2]});
vector<long long> best(n + 1, 0);
for (int x = 2; x <= n; x++) {
best[x] = best[x - 1];
for (auto& [s, t] : endsAt[x])
best[x] = max(best[x], best[s] + x - s + t);
}
return best[n];
}
};function maxTaxiEarnings(n, rides) {
const endsAt = Array.from({ length: n + 1 }, () => []);
for (const r of rides) endsAt[r[1]].push(r);
const best = new Array(n + 1).fill(0);
for (let x = 2; x <= n; x++) {
best[x] = best[x - 1];
for (const r of endsAt[x])
best[x] = Math.max(best[x], best[r[0]] + x - r[0] + r[2]);
}
return best[n];
}Edge cases to test
- A ride ending exactly where the next one starts (both can be taken)
- Many rides ending at the same point
- One long ride versus several short rides covering the same stretch
- Totals above 2^31, so the answer needs 64 bits
Hints
Hint 1
This is weighted interval scheduling: pick non-overlapping rides with maximum total earnings, where a ride ending at x and one starting at x do not overlap.
Hint 2
Let best[x] be the most you can earn with the car at point x. Either no ride ends at x (best[x - 1]), or some ride [s, x, t] ends there (best[s] + x - s + t).
Hint 3
Group rides by their end point so each point only looks at the rides ending there.
FAQ
What is the best time complexity for Maximum Earnings From Taxi?
Optimal (DP over road points) runs in O(n + m) time and O(n + m) extra space. Each point is visited once and each ride is checked once at its end point.
Which pattern does Maximum Earnings From Taxi use?
It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).
Is there a brute force solution for Maximum Earnings From Taxi?
Yes. Brute force (DP over rides, scan all earlier rides) takes O(m²) time and O(m) space. Sort rides by end.
Which edge cases should I test for Maximum Earnings From Taxi?
A ride ending exactly where the next one starts (both can be taken); Many rides ending at the same point; One long ride versus several short rides covering the same stretch; Totals above 2^31, so the answer needs 64 bits.