A taxi driver knows the pick-up and drop-off locat...

We can solve this problem by realizing that it is a weighted interval scheduling problem. Each ride can be seen as an interval $[pickup_i, drop_i]$ with a profit (or weight) given by

$$\text{profit}_i = (\text{drop}_i - \text{pickup}_i) + \text{tip}_i.$$

Because the taxi can only serve one passenger at a time (i.e. the rides cannot overlap), we want to select a set of non‐overlapping rides that maximizes the sum of profits.

A common way to solve weighted interval scheduling is as follows:

1. Sort the rides by their drop-off location.

2. For each ride, use binary search to find the last ride that ends at or before the current ride’s pickup. Let’s call its index $j$. This tells us that if we take the current ride, then we can add its profit to the best answer obtained up to ride $j$.

3. Use dynamic programming (DP) to choose whether to take or skip a ride. If we let dp[i] be the maximum earning possible using the first $i$ rides (when the rides are sorted by drop), then the recurrence is

   $$dp[i] = \max(dp[i-1],\ dp[j+1] + \text{profit of ride } i-1)$$

   (Here we use $j+1$ because we use a DP array of size $n+1$ with dp[0]=0.)

Below is one acceptable Java solution:

---

java
import java.util.Arrays;

public class TaxiDriver {

    // Helper class to hold ride information.
    static class Ride {
        long pickup;
        long drop;
        long profit; // profit = (drop - pickup) + tip

        public Ride(long pickup, long drop, int tip) {
            this.pickup = pickup;
            this.drop = drop;
            this.profit = (drop - pickup) + tip;
        }
    }

    /**
     * Given arrays of pickup locations, drop-off locations, and tips, 
     * returns the maximum amount the taxi driver can earn.
     *
     * @param pickup an array of pickup locations (in km)
     * @param drop   an array of drop-off locations (in km)
     * @param tip    an array of tips offered by the riders
     * @return the maximum total earnings
     */
    public static long taxiDriver(long[] pickup, long[] drop, int[] tip) {
        int n = pickup.length;
        // Create an array of rides.
        Ride[] rides = new Ride[n];
        for (int i = 0; i < n; i++) {
            rides[i] = new Ride(pickup[i], drop[i], tip[i]);
        }

        // Sort the rides by drop-off location.
        Arrays.sort(rides, (a, b) -> Long.compare(a.drop, b.drop));

        // Create a DP array where dp[i] will be the maximum earnings using the first i rides.
        long[] dp = new long[n + 1];
        dp[0] = 0;

        // For binary search, store the drop times in a separate array.
        long[] endTimes = new long[n];
        for (int i = 0; i < n; i++) {
            endTimes[i] = rides[i].drop;
        }

        // Process each ride.
        for (int i = 1; i <= n; i++) {
            // Current ride is rides[i-1] (because dp array is 1-indexed).
            Ride currentRide = rides[i - 1];
            
            // Find the last ride that ends at or before currentRide.pickup.
            // We want the rightmost index j such that endTimes[j] <= currentRide.pickup.
            int j = Arrays.binarySearch(endTimes, 0, i - 1, currentRide.pickup);
            if (j < 0) {
                // If not found, binarySearch returns (-(insertion point) - 1).
                // The insertion point is the index of the first element greater than currentRide.pickup.
                j = -j - 2;
            }
            
            // Candidate earnings if we take the current ride:
            // dp[j+1] is the best earnings before current ride's pickup.
            long takeRide = (j >= 0 ? dp[j + 1] : 0) + currentRide.profit;
            
            // Option 1: Skip current ride; Option 2: Take current ride.
            dp[i] = Math.max(dp[i - 1], takeRide);
        }
        
        return dp[n];
    }
    
    // Example usage
    public static void main(String[] args) {
        long[] pickup = {0, 2, 9, 10, 11, 12};
        long[] drop   = {5, 9, 11, 11, 14, 17};
        int[] tip     = {1, 2, 3, 2, 2, 1};

        long maxEarnings = taxiDriver(pickup, drop, tip);
        System.out.println("Maximum earnings: " + maxEarnings);  // Expected output: 20
    }
}

---

Explanation

1. Ride Class:

   • The Ride class holds the pickup, drop, and computed profit for each ride.

2. Sorting:

   • We sort the rides by their drop-off locations. This helps in easily finding the latest ride that does not conflict with the current one.

3. Dynamic Programming Array:

   • dp[i] holds the maximum earnings possible by considering the first $i$ rides (after sorting).
   • For each ride (indexed by $i-1$ in the rides array), we use binary search on the endTimes array to find the ride with the largest drop-off that is less than or equal to the current ride’s pickup. Let that index be $j$.
   • If we take the current ride, our total earnings become dp[j+1] + currentRide.profit.
   • Otherwise, we just carry over dp[i-1] (skipping the current ride).
   • We take the maximum of these two choices.

4. Example:

   • With the example input, the DP process will eventually compute the maximum earning as 20, matching the provided explanation.

This solution meets the constraints and should work efficiently even when there are up to $10^4$ rides.