2008. Maximum Earnings From Taxi LeetCode Solution

In this guide, you will get 2008. Maximum Earnings From Taxi LeetCode Solution with the best time and space complexity. The solution to Maximum Earnings From Taxi problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Earnings From Taxi solution in C++
Maximum Earnings From Taxi solution in Java
Maximum Earnings From Taxi solution in Python
Additional Resources

2008. Maximum Earnings From Taxi LeetCode Solution image

Problem Statement of Maximum Earnings From Taxi

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 <= 105
1 <= rides.length <= 3 * 104
rides[i].length == 3
1 <= starti < endi <= n
1 <= tipi <= 105

Complexity Analysis

Time Complexity: O(n + |\texttt{rides}|)
Space Complexity: O(n + |\texttt{rides}|)

2008. Maximum Earnings From Taxi LeetCode Solution in C++

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];
  }
};
/* code provided by PROGIEZ */

2008. Maximum Earnings From Taxi LeetCode Solution in Java

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];
  }
}
// code provided by PROGIEZ

2008. Maximum Earnings From Taxi LeetCode Solution in Python

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]
 # code by PROGIEZ