Maximum Earnings From Taxi

medium dp sorting

Problem

There are n points 1..n on a road. Each ride rides[i] = [start, end, tip] earns you (end − start) + tip. You may only drive one passenger at a time and a ride ending at x lets the next ride begin at x. Return the maximum money you can earn.

Inputn = 5, rides = [[2,5,4],[1,5,1]]

Output7

Ride [2,5,4] earns (5−2)+4 = 7, beating [1,5,1]'s (5−1)+1 = 5.

rides (s,e,tip ; ...)

def max_taxi_earnings(n, rides):
    by_end = [[] for _ in range(n + 1)]
    for s, e, tip in rides:
        by_end[e].append((s, e - s + tip))
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i - 1]
        for s, gain in by_end[i]:
            dp[i] = max(dp[i], dp[s] + gain)
    return dp[n]

function maxTaxiEarnings(n, rides) {
  const byEnd = Array.from({ length: n + 1 }, () => []);
  for (const [s, e, tip] of rides) byEnd[e].push([s, e - s + tip]);
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i - 1];
    for (const [s, gain] of byEnd[i]) {
      dp[i] = Math.max(dp[i], dp[s] + gain);
    }
  }
  return dp[n];
}

class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        List<int[]>[] byEnd = new List[n + 1];
        for (int i = 0; i <= n; i++) byEnd[i] = new ArrayList<>();
        for (int[] r : rides) byEnd[r[1]].add(new int[]{r[0], r[1] - r[0] + r[2]});
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            for (int[] r : byEnd[i]) dp[i] = Math.max(dp[i], dp[r[0]] + r[1]);
        }
        return dp[n];
    }
}

long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
    vector<vector<pair<int,int>>> byEnd(n + 1);
    for (auto& r : rides) byEnd[r[1]].push_back({r[0], r[1] - r[0] + r[2]});
    vector<long long> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        for (auto& [s, gain] : byEnd[i]) dp[i] = max(dp[i], dp[s] + gain);
    }
    return dp[n];
}

Explanation

Let dp[i] be the most money we can have earned by the time we are sitting at point i. Each point on the road becomes a state, and we fill them left to right.

At point i we have two choices. We can do nothing here and carry the best we had at i−1, giving dp[i] = dp[i−1]. Or we can finish a ride that ends exactly at i: if that ride started at s and earns gain = (i − s) + tip, then taking it gives dp[s] + gain.

To find rides ending at i quickly, we bucket every ride by its end point first. Then dp[i] is just the maximum of "skip" and every "take a ride ending here" option.

Because a ride ending at i started at some earlier s, the value dp[s] is already computed — the left-to-right order guarantees no forward dependency. The final answer is dp[n].

Example: n = 5, rides [2,5,4] and [1,5,1], both end at 5. Their gains are (5−2)+4 = 7 and (5−1)+1 = 5. So dp[5] = max(dp[4], dp[2]+7, dp[1]+5) = 7.

Time: O(n + m) Space: O(n + m)