Skip to content

2008. Maximum Earnings From Taxi 👍

Approach 1: Iterate start

  • Time: $O(n + |\texttt{rides}|)$
  • Space: $O(n + |\texttt{rides}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
    vector<vector<pair<int, int>>> startToEndAndEarns(n);
    // dp[i] := the maximum dollars you can earn starting at i
    vector<long> dp(n + 1);

    for (const vector<int>& ride : rides) {
      const int start = ride[0];
      const int end = ride[1];
      const int tip = ride[2];
      const int earn = end - start + tip;
      startToEndAndEarns[start].emplace_back(end, earn);
    }

    for (int i = n - 1; i >= 1; --i) {
      dp[i] = dp[i + 1];
      for (const auto& [end, earn] : startToEndAndEarns[i])
        dp[i] = max(dp[i], dp[end] + earn);
    }

    return dp[1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public long maxTaxiEarnings(int n, int[][] rides) {
    List<Pair<Integer, Integer>>[] startToEndAndEarns = new List[n];
    // dp[i] := the maximum dollars you can earn starting at i
    long[] dp = new long[n + 1];

    for (int i = 1; i < n; ++i)
      startToEndAndEarns[i] = new ArrayList<>();

    for (int[] ride : rides) {
      final int start = ride[0];
      final int end = ride[1];
      final int tip = ride[2];
      final int earn = end - start + tip;
      startToEndAndEarns[start].add(new Pair<>(end, earn));
    }

    for (int i = n - 1; i >= 1; --i) {
      dp[i] = dp[i + 1];
      for (Pair<Integer, Integer> pair : startToEndAndEarns[i]) {
        final int end = pair.getKey();
        final int earn = pair.getValue();
        dp[i] = Math.max(dp[i], dp[end] + earn);
      }
    }

    return dp[1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maxTaxiEarnings(self, n: int, rides: list[list[int]]) -> int:
    startToEndAndEarns = [[] for _ in range(n)]
    # dp[i] := the maximum dollars you can earn starting at i
    dp = [0] * (n + 1)

    for start, end, tip in rides:
      earn = end - start + tip
      startToEndAndEarns[start].append((end, earn))

    for i in range(n - 1, 0, -1):
      dp[i] = dp[i + 1]
      for end, earn in startToEndAndEarns[i]:
        dp[i] = max(dp[i], dp[end] + earn)

    return dp[1]

Approach 2: Iterate end

  • Time: $O(n + |\texttt{rides}|)$
  • Space: $O(n + |\texttt{rides}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
    vector<vector<pair<int, int>>> endToStartAndEarns(n + 1);
    // dp[i] := the maximum dollars you can earn ending in i
    vector<long> dp(n + 1);

    for (const vector<int>& ride : rides) {
      const int start = ride[0];
      const int end = ride[1];
      const int tip = ride[2];
      const int earn = end - start + tip;
      endToStartAndEarns[end].emplace_back(start, earn);
    }

    for (int i = 1; i <= n; ++i) {
      dp[i] = dp[i - 1];
      for (const auto& [start, earn] : endToStartAndEarns[i])
        dp[i] = max(dp[i], dp[start] + earn);
    }

    return dp[n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public long maxTaxiEarnings(int n, int[][] rides) {
    List<Pair<Integer, Integer>>[] endToStartAndEarns = new List[n + 1];
    // dp[i] := the maximum dollars you can earn ending in i
    long[] dp = new long[n + 1];

    for (int i = 1; i <= n; ++i)
      endToStartAndEarns[i] = new ArrayList<>();

    for (int[] ride : rides) {
      final int start = ride[0];
      final int end = ride[1];
      final int tip = ride[2];
      final int earn = end - start + tip;
      endToStartAndEarns[end].add(new Pair<>(start, earn));
    }

    for (int i = 1; i <= n; ++i) {
      dp[i] = dp[i - 1];
      for (Pair<Integer, Integer> pair : endToStartAndEarns[i]) {
        final int start = pair.getKey();
        final int earn = pair.getValue();
        dp[i] = Math.max(dp[i], dp[start] + earn);
      }
    }

    return dp[n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maxTaxiEarnings(self, n: int, rides: list[list[int]]) -> int:
    endToStartAndEarns = [[] for _ in range(n + 1)]
    # dp[i] := the maximum dollars you can earn starting at i
    dp = [0] * (n + 1)

    for start, end, tip in rides:
      earn = end - start + tip
      endToStartAndEarns[end].append((start, earn))

    for i in range(1, n + 1):
      dp[i] = dp[i - 1]
      for start, earn in endToStartAndEarns[i]:
        dp[i] = max(dp[i], dp[start] + earn)

    return dp[n]