Get started

Maximum Earnings From Taxi — Medium Problem & Solution

You drive a taxi along a road with points 1 to n, always moving from point 1 towards point n — you can never turn back.

Problem statement

You drive a taxi along a road with points 1 to n, always moving from point 1 towards point n — you can never turn back.

rides[i] = [start_i, end_i, tip_i] is a passenger who wants to go from start_i to end_i and tips tip_i. Carrying that passenger earns end_i - start_i + tip_i. You can carry at most one passenger at a time, but you may pick someone up at the very point where you drop the previous passenger off.

Return the maximum amount you can earn.

CodeKairo bound: tips are capped at 10^4 (LeetCode allows 10^5) so that the answer always fits in a 32-bit integer.

Example 1

Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7
Explanation: Take the first passenger: 5 - 2 + 4.

Example 2

Input: n = 10, rides = [[1,4,2],[4,7,1],[2,9,3]]
Output: 10
Explanation: The two short rides earn 5 + 4 = 9; the long one alone earns 7 + 3 = 10.

Example 3

Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20

Constraints

  • 1 <= n <= 10^5
  • 1 <= rides.length <= 3 * 10^4
  • rides[i].length == 3
  • 1 <= start_i < end_i <= n
  • 1 <= tip_i <= 10^4

How to solve Maximum Earnings From Taxi

Sweep the road left to right. The best earnings at point p either carry over from p - 1 or come from finishing some ride exactly at p, which started at a point whose best earnings are already known.

Approach

  1. Bucket (or sort) the rides by end point.
  2. dp[1] = 0. For p = 2..n: dp[p] = dp[p - 1], then for each ride [s, p, tip] ending here, dp[p] = max(dp[p], dp[s] + p - s + tip).
  3. Return dp[n].

Why it works

Any valid schedule is a chain of non-overlapping rides in order of position. The last ride finishing at or before p either ends exactly at p (and the rest of the schedule is a valid schedule up to its start s, worth at most dp[s]) or ends earlier (covered by dp[p - 1]). Induction on p shows dp[p] is the true optimum.

Complexity

  • Time — O(n + r log r)
  • Space — O(n + r)

Pitfalls

  • A new ride may start at the same point the previous one ends — compare with <=, not <.
  • The base fare end - start counts too, not just the tip.
  • With LeetCode's original bounds the answer needs 64 bits; the tightened tip bound keeps it under 2^31.

Reference solution

Python

from typing import List

def maxTaxiEarnings(n: int, rides: List[List[int]]) -> int:
    ending = [[] for _ in range(n + 1)]
    for s, e, tip in rides:
        ending[e].append((s, e - s + tip))
    dp = [0] * (n + 1)
    for p in range(2, n + 1):
        best = dp[p - 1]
        for s, gain in ending[p]:
            if dp[s] + gain > best:
                best = dp[s] + gain
        dp[p] = best
    return dp[n]

JavaScript

var maxTaxiEarnings = function(n, rides) {
    var rs = rides.slice().sort(function(a, b) { return a[1] - b[1]; });
    var dp = new Array(n + 1).fill(0);
    var ptr = 0;
    for (var p = 1; p <= n; p++) {
        if (p > 1) dp[p] = dp[p - 1];
        while (ptr < rs.length && rs[ptr][1] === p) {
            var r = rs[ptr];
            var cand = dp[r[0]] + r[1] - r[0] + r[2];
            if (cand > dp[p]) dp[p] = cand;
            ptr++;
        }
    }
    return dp[n];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming