Problem

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.

Examples

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.

Solution

Method 1 - Sorting + Binary Search

Here is the approach:

  1. Sort Rides:
    • First, sort the rides based on their end points to facilitate processing in a single pass with dynamic programming.
  2. Dynamic Programming Array:
    • Use a dp array where dp[i] represents the maximum earnings achievable by the time we reach point i.
  3. Job Scheduling:
    • For each ride, calculate the profit and use previously computed dp values to make decisions.
    • Update the dp array considering whether to take a new ride or not.
  4. Binary Search:
    • Use binary search to quickly find the rides that end before the start of a given ride.

Code

Java
class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        Arrays.sort(rides, Comparator.comparingInt(a -> a[1]));
        long[] dp = new long[n + 1];
        int idx = 0;
        for (int i = 1; i <= n; i++) {
            if (i > 1) dp[i] = dp[i - 1]; // carry forward the max profit so far
            while (idx < rides.length && rides[idx][1] == i) {
                int start = rides[idx][0], end = rides[idx][1], tip = rides[idx][2];
                dp[end] = Math.max(dp[end], dp[start] + (end - start + tip));
                idx++;
            }
        }
        return dp[n];
    }
}
Python
class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort(key=lambda x: x[1])
        dp = [0] * (n + 1)
        idx = 0

        for i in range(1, n + 1):
            if i > 1:
                dp[i] = dp[i - 1]  # Carry forward the max profit so far
            while idx < len(rides) and rides[idx][1] == i:
                start, end, tip = rides[idx]
                dp[end] = max(dp[end], dp[start] + (end - start + tip))
                idx += 1

        return dp[-1]

Complexity

  • ⏰ Time complexity: O(k log k),  where k is the number of rides.
    • Sorting the rides - O(k log k)
    • Filling the dp array: O(k log k) due to the binary search.
  • 🧺 Space complexity: O(n + k), where n is the number of points and k is the number of rides.