# Maximum Earnings From Taxi
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-earnings-from-taxi)
Canonical: https://scaleengineer.com/dsa/problems/maximum-earnings-from-taxi
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Myntra](https://scaleengineer.com/companies/myntra)
---
## 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.

**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`

# Approaches
## Brute-Force Recursion
This approach uses a straightforward recursive method to explore all possible combinations of rides. It defines a function that, for each point on the road, decides between not taking a ride or taking one of the available rides starting at that point. It recursively calculates the potential earnings for each choice and returns the maximum.
**Time:** Exponential - O(2^n) in the worst-case scenarios. The function may recompute solutions for the same points multiple times, leading to an exponential growth in the number of operations. · **Space:** O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can go up to `n` in the worst case.
**Pros:** Simple to understand and implement.; Directly models the decision-making process at each point.
**Cons:** Extremely inefficient due to a massive number of redundant computations.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The brute-force recursive solution attempts to find the optimal earnings by exploring every valid sequence of rides. We define a function `solve(i)` that computes the maximum earnings from point `i` to `n`. At each point `i`, the function considers two main possibilities: skipping any ride and moving to `i+1`, or taking one of the available rides that start at `i`. If a ride is taken from `i` to `j`, the total earnings for that path are the ride's profit plus the result of a recursive call `solve(j)`. The function then returns the maximum earnings found among all these possibilities. This method leads to an exponential number of calls for the same subproblems (e.g., `solve(k)` might be called from different paths), making it highly inefficient.

```java
import java.util.*;

class Solution {
    Map<Integer, List<int[]>> ridesByStart;
    int N;

    public long maxTaxiEarnings(int n, int[][] rides) {
        this.N = n;
        this.ridesByStart = new HashMap<>();
        for (int[] ride : rides) {
            // Store rides by their start point for easy lookup
            // rideInfo: [end, tip]
            ridesByStart.computeIfAbsent(ride[0], k -> new ArrayList<>()).add(new int[]{ride[1], ride[2]});
        }
        return solve(1);
    }

    private long solve(int currentPoint) {
        if (currentPoint > N) {
            return 0;
        }

        // Option 1: Don't take any ride, move to the next point
        long maxEarnings = solve(currentPoint + 1);

        // Option 2: Take a ride starting at currentPoint
        if (ridesByStart.containsKey(currentPoint)) {
            for (int[] rideInfo : ridesByStart.get(currentPoint)) {
                int end = rideInfo[0];
                int tip = rideInfo[1];
                long earnings = (long)end - currentPoint + tip;
                maxEarnings = Math.max(maxEarnings, earnings + solve(end));
            }
        }
        return maxEarnings;
    }
}
```
### Algorithm
- Define a recursive function, let's call it `solve(currentPoint)`, which calculates the maximum earnings possible starting from `currentPoint` all the way to `n`.
- **Base Case:** If `currentPoint` is greater than `n`, it means we are past the destination, so no more earnings can be made. Return 0.
- **Recursive Step:** At any `currentPoint`, we have several choices:
  1. **Don't pick up any passenger:** We can simply drive to the next point, `currentPoint + 1`. The earnings from this choice would be whatever we can make from `currentPoint + 1` onwards, which is `solve(currentPoint + 1)`.
  2. **Pick up a passenger:** We look for all available rides that start at `currentPoint`. For each such ride `[start, end, tip]` where `start == currentPoint`, we can choose to take it. The earnings for this choice would be the profit from this single ride (`end - start + tip`) plus the maximum earnings we can get after completing the ride, which is `solve(end)`.
- The function `solve(currentPoint)` returns the maximum value among all these choices.
- The initial call to start the process would be `solve(1)`.

## Dynamic Programming on Rides (Weighted Interval Scheduling)
This approach reframes the problem as a classic dynamic programming pattern known as Weighted Interval Scheduling. Each ride is treated as a 'job' with a start time, end time, and a weight (profit). The goal is to select a set of non-overlapping jobs to maximize the total weight. By sorting the rides by their end points, we can build up a solution iteratively.
**Time:** O(R log R) - Sorting the rides takes O(R log R). The DP calculation involves a loop of size `R`, and inside each iteration, we perform a binary search which takes O(log R). Thus, the total time is dominated by O(R log R). · **Space:** O(R) - We need an array of size `R` (the number of rides) to store the DP states.
**Pros:** More efficient than the brute-force approach.; Space complexity is O(R), which is better than the DP on points approach if `n` is much larger than `R`.
**Cons:** Can be slower than the DP on points approach if `R log R` is greater than `n + R`.; The logic involving sorting and binary search is slightly more complex to implement correctly.
### Explanation
In this method, we treat each ride as an interval with an associated profit. The core idea is to make a decision for each ride: either take it or leave it.

First, we sort all rides by their `end` point. This allows us to process rides in the order they finish. We use a DP array, `dp`, where `dp[i]` stores the maximum earnings considering rides up to index `i` in the sorted array.

For each ride `i`, we have two choices:
1.  **Include ride `i`:** We get its profit (`end - start + tip`). To this, we must add the maximum profit from rides that are compatible, i.e., rides that end before ride `i` begins. Since the rides are sorted by `end` point, we need to find the maximum profit from rides `0` to `i-1` that finish by `rides[i].start`. This can be found by locating the index `j` of the last ride ending before or at `rides[i].start` and taking `dp[j]`. This search for `j` is optimized using binary search.
2.  **Exclude ride `i`:** The maximum profit is simply the maximum profit obtainable from rides `0` to `i-1`, which is `dp[i-1]`.

`dp[i]` is the maximum of these two choices. The final answer is the maximum earnings after considering all rides, which is `dp[R-1]`. 

```java
import java.util.Arrays;

class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        Arrays.sort(rides, (a, b) -> Integer.compare(a[1], b[1]));

        int numRides = rides.length;
        if (numRides == 0) return 0;
        
        long[] dp = new long[numRides];

        for (int i = 0; i < numRides; i++) {
            int start = rides[i][0];
            int end = rides[i][1];
            int tip = rides[i][2];
            long profit = (long)end - start + tip;

            // Option 1: Take this ride
            long currentProfit = profit;
            int prevRideIndex = findLastNonConflicting(rides, i);
            if (prevRideIndex != -1) {
                currentProfit += dp[prevRideIndex];
            }

            // Option 2: Don't take this ride
            long prevMaxProfit = (i > 0) ? dp[i - 1] : 0;

            dp[i] = Math.max(currentProfit, prevMaxProfit);
        }

        return dp[numRides - 1];
    }

    // Binary search to find the index of the last ride that ends at or before `startTime` of the current ride.
    private int findLastNonConflicting(int[][] rides, int currentIndex) {
        int low = 0;
        int high = currentIndex - 1;
        int result = -1;
        int targetStartTime = rides[currentIndex][0];

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (rides[mid][1] <= targetStartTime) {
                result = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }
}
```
### Algorithm
- **Preprocessing:** Calculate the profit for each ride, where `profit = end - start + tip`.
- **Sort:** Sort the `rides` array based on their `end` points in ascending order.
- **DP Initialization:** Create a `dp` array of size equal to the number of rides, `R`. `dp[i]` will store the maximum earnings considering the first `i+1` rides from the sorted list.
- **DP Iteration:** Iterate through the sorted rides from `i = 0` to `R-1`.
  - For each ride `i`, calculate the profit of taking this ride: `profit_i`.
  - Find the latest non-conflicting ride `j` that finishes before ride `i` starts (i.e., `rides[j].end <= rides[i].start`). This can be done efficiently using binary search on the `end` points of rides `0` to `i-1`.
  - The total earnings if we take ride `i` is `profit_i + dp[j]` (if such a `j` exists).
  - The earnings if we *don't* take ride `i` is `dp[i-1]` (the max earnings from previous rides).
  - Set `dp[i] = max(profit_with_ride_i, profit_without_ride_i)`.
- **Result:** The last element of the `dp` array, `dp[R-1]`, will hold the maximum possible earnings.

## Dynamic Programming on Points
This is the most efficient approach for the given constraints. It uses dynamic programming where the state is tied to the points on the road. We build a `dp` array where `dp[i]` stores the maximum earnings we can have by the time we reach point `i`. The solution is built iteratively by considering the maximum earnings from the previous point and the potential earnings from any rides that drop off a passenger at the current point.
**Time:** O(n + R) - Preprocessing the `R` rides into a map takes O(R). The main loop runs `n` times. Inside the loop, we access the map. Over all `n` iterations, the inner loop (iterating over rides ending at `i`) will execute a total of `R` times. Therefore, the total time complexity is O(n + R). · **Space:** O(n + R) - Requires O(n) for the DP array and O(R) for the map to store the preprocessed rides.
**Pros:** Most efficient time complexity for the given constraints.; The DP state and transition directly model the problem's progression along the road, making it intuitive.
**Cons:** The space complexity is O(n + R), which can be large if `n` is very large.
### Explanation
This dynamic programming approach defines its state based on the location on the road. We let `dp[i]` be the maximum possible earnings after arriving at point `i`. Our goal is to compute `dp[n]`.

The transition for `dp[i]` is based on what happens at point `i`. To arrive at point `i`, we could have either driven from `i-1` without a passenger, or we could have just completed a ride that ended at `i`.

1.  **Base case:** `dp[0] = 0`. No earnings before starting.
2.  **Transition:** For each point `i` from 1 to `n`:
    - The default maximum earning is inherited from the previous point: `dp[i] = dp[i-1]`.
    - We then check if any rides end at point `i`. To do this efficiently, we first preprocess the `rides` into a map where keys are end points. For every ride `[start, end, tip]` with `end == i`, we calculate a potential new maximum earning: `dp[start] + (end - start + tip)`. This represents the earnings from an optimal path to `start`, followed by taking this specific ride.
    - We update `dp[i]` with the maximum value found among `dp[i-1]` and all possibilities from rides ending at `i`.

This ensures that at each point `i`, `dp[i]` holds the optimal earnings. The final answer is `dp[n]`.

```java
import java.util.*;

class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        // Group rides by their end point for efficient lookup.
        // The map stores: endPoint -> List of {startPoint, tip}
        Map<Integer, List<int[]>> ridesByEnd = new HashMap<>();
        for (int[] ride : rides) {
            ridesByEnd.computeIfAbsent(ride[1], k -> new ArrayList<>()).add(new int[]{ride[0], ride[2]});
        }

        // dp[i] will store the maximum earnings up to point i.
        long[] dp = new long[n + 1];

        for (int i = 1; i <= n; i++) {
            // Option 1: Don't end a ride at point i. Earnings are same as up to i-1.
            dp[i] = dp[i - 1];

            // Option 2: Check if any rides end at point i.
            if (ridesByEnd.containsKey(i)) {
                for (int[] rideInfo : ridesByEnd.get(i)) {
                    int start = rideInfo[0];
                    int tip = rideInfo[1];
                    long profit = (long)i - start + tip;
                    // Compare with current max and update if this path is better.
                    dp[i] = Math.max(dp[i], dp[start] + profit);
                }
            }
        }

        return dp[n];
    }
}
```
### Algorithm
- **Preprocessing:** Group the rides by their `end` point. A `HashMap<Integer, List<int[]>>` is an effective way to do this, mapping each `end` point to a list of rides that finish there.
- **DP Initialization:** Create a `dp` array of size `n + 1`. `dp[i]` will represent the maximum earnings achievable up to point `i` on the road. Initialize all `dp` values to 0.
- **DP Iteration:** Iterate from `i = 1` to `n`.
  - For each point `i`, we have two main possibilities to determine `dp[i]`:
    1. **No ride ends at `i`:** In this case, we just drove from point `i-1` to `i` without a passenger. The maximum earnings are the same as the earnings up to point `i-1`. So, we set `dp[i] = dp[i-1]`.
    2. **One or more rides end at `i`:** For each ride `[start, end, tip]` where `end == i`, we calculate a potential new maximum earning. This would be the earnings from this ride (`end - start + tip`) plus the maximum earnings we had accumulated up to the `start` point of this ride (`dp[start]`).
  - We update `dp[i]` to be the maximum of `dp[i-1]` and all potential earnings calculated from rides ending at `i`.
- **Result:** The final answer is the value stored in `dp[n]`, which represents the maximum earnings after reaching the final destination.

# Solutions
### Java

```java
class Solution { private int m ; private int [][] rides ; private Long [] f ; public long maxTaxiEarnings ( int n , int [][] rides ) { Arrays . sort ( rides , ( a , b ) -> a [ 0 ] - b [ 0 ]); m = rides . length ; f = new Long [ m ]; this . rides = rides ; return dfs ( 0 ); } private long dfs ( int i ) { if ( i >= m ) { return 0 ; } if ( f [ i ] != null ) { return f [ i ]; } int [] r = rides [ i ]; int st = r [ 0 ], ed = r [ 1 ], tip = r [ 2 ]; int j = search ( ed , i + 1 ); return f [ i ] = Math . max ( dfs ( i + 1 ), dfs ( j ) + ed - st + tip ); } private int search ( int x , int l ) { int r = m ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( rides [ mid ][ 0 ] >= x ) { r = mid ; } else { l = mid + 1 ; } } return l ; } }
```

### CPP

```cpp
class Solution {
public:
  long long maxTaxiEarnings(int n, vector<vector<int>> &rides) {
    sort(rides.begin(), rides.end());
    int m = rides.size();
    long long f[m];
    memset(f, -1, sizeof(f));
    function<long long(int)> dfs = [&](int i) -> long long {
      if (i >= m) {
        return 0;
      }
      if (f[i] != -1) {
        return f[i];
      }
      auto &r = rides[i];
      int st = r[0], ed = r[1], tip = r[2];
      int j = lower_bound(rides.begin() + i + 1, rides.end(), ed,
                          [](auto &a, int val) { return a[0] < val; }) -
              rides.begin();
      return f[i] = max(dfs(i + 1), dfs(j) + ed - st + tip);
    };
    return dfs(0);
  }
};

```

### Python

```python
class Solution : def maxTaxiEarnings ( self , n : int , rides : List [ List [ int ]]) -> int : @ cache def dfs ( i : int ) -> int : if i >= len ( rides ): return 0 st , ed , tip = rides [ i ] j = bisect_left ( rides , ed , lo = i + 1 , key = lambda x : x [ 0 ]) return max ( dfs ( i + 1 ), dfs ( j ) + ed - st + tip ) rides . sort () return dfs ( 0 )
```