Maximum Earnings From Taxi

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.

• 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.

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].

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];
    }
}