2008. Maximum Earnings From Taxi - Detailed Explanation

Problem Statement

You are given an integer n and a list of taxi rides, where each ride is represented as an array of three integers:

• start: the starting location of the ride,
• end: the ending location of the ride, and
• tip: the tip earned for that ride.

For each ride, the taxi driver earns an amount equal to (end - start + tip). However, the driver can only accept rides that do not overlap – meaning, after finishing one ride, the next ride must have a starting location greater than or equal to the ending location of the previous ride.

Your goal is to determine the maximum total earnings that the taxi driver can accumulate by optimally selecting a subset of non-overlapping rides.

Example 1

• Input:
  n = 10
  rides = [[1, 3, 2], [2, 5, 4], [4, 10, 3]]
• Output: 13
• Explanation:
  • Ride 1: From 1 to 3 with tip 2 yields an earning of (3 - 1 + 2) = 4.
  • Ride 3: From 4 to 10 with tip 3 yields an earning of (10 - 4 + 3) = 9.
  • These rides do not overlap (since ride 1 ends at 3 and ride 3 starts at 4), and the total earnings are 4 + 9 = 13.
  • Note that taking ride 2 (from 2 to 5) alone would yield (5 - 2 + 4) = 7, which is less than 13.

Example 2

• Input:
  n = 20
  rides = [[2, 11, 6], [2, 4, 4], [7, 12, 4], [10, 11, 2], [12, 18, 3], [7, 13, 5]]
• Output: 24
• Explanation:
  One optimal solution is to choose:
  • Ride [2, 4, 4] with earnings 4 - 2 + 4 = 6,
  • followed by ride [7, 12, 4] with earnings 12 - 7 + 4 = 9, and
  • then ride [12, 18, 3] with earnings 18 - 12 + 3 = 9.
    The total earnings are 6 + 9 + 9 = 24.

Constraints

• 1 <= n <= 10⁹
• 1 <= rides.length <= 3 * 10⁵
• For each ride, 1 <= start < end <= n
• 0 <= tip <= 10⁵

Hints

1. Weighted Interval Scheduling:
   Notice that each ride has a “weight” (its earning) and a time interval [start, end]. The problem can be modeled similarly to the weighted interval scheduling problem.

2. Sorting and Binary Search:
   Sort the rides by their start time. For each ride, you can use binary search to quickly find the next ride that can be taken (i.e., the ride with a start time greater than or equal to the current ride’s end).

3. Dynamic Programming:
   Use a DP array where dp[i] represents the maximum earnings achievable from the i-th ride onward. For each ride, decide whether to take it (and add its profit plus the DP value of the next valid ride) or skip it.

Approach 1: Brute Force (Not Recommended)

Explanation

A naïve solution is to explore every possible subset of non-overlapping rides, calculate the total earnings for each, and return the maximum. This approach would involve recursively choosing rides and backtracking if they overlap.

Step-by-Step Walkthrough

1. For each ride, consider two choices:
   • Take the ride: If its start time is after the previous ride’s end, add its profit (end - start + tip) and move on to the next possible ride.
   • Skip the ride: Move on to the next ride without adding its profit.
2. Track the maximum total earnings from all these choices.

Drawbacks

• The brute-force method has an exponential time complexity since you must explore every subset.
• It is not feasible given the problem constraints (up to 300,000 rides).

Approach 2: Dynamic Programming with Binary Search (Optimal)

Explanation

This problem is best solved by combining dynamic programming with binary search, following a strategy similar to weighted interval scheduling.

Steps Involved

1. Sort the Rides:
   Sort the list of rides by their start time.

2. Precompute Profit for Each Ride:
   For each ride, calculate its profit as (end - start + tip).

3. Prepare for Binary Search:
   Create an array (or list) of just the start times from the sorted rides. This will help quickly find the next ride that can be taken.

4. Dynamic Programming Recurrence:
   Use a DP array where dp[i] represents the maximum earnings from the i-th ride onward.

   • For ride i, use binary search to find the smallest index j such that rides[j][0] >= rides[i][1].
   • The recurrence is:
     dp[i] = max(dp[i+1], profit[i] + (dp[j] if j exists, else 0))
   • This means:
     • Skip ride i: Earn dp[i+1].
     • Take ride i: Earn its profit plus the best earnings starting from ride j.

5. Final Answer:
   The answer will be stored in dp[0], which represents the maximum earnings starting from the first ride.

Step-by-Step Walkthrough with Example

For Example 1 (n = 10, rides = [[1, 3, 2], [2, 5, 4], [4, 10, 3]]):

• Sort the rides: They are already sorted by start time.
• Calculate profits:
  • Ride 1: 3 - 1 + 2 = 4
  • Ride 2: 5 - 2 + 4 = 7
  • Ride 3: 10 - 4 + 3 = 9
• DP Calculation:
  • Starting from the last ride: dp[2] = 9 (only ride 3 available).
  • For ride 2:
    • Next ride’s start must be ≥ 5; ride 3 starts at 4, so no valid next ride exists.
    • Thus, dp[1] = max(dp[2], 7) = max(9, 7) = 9.
  • For ride 1:
    • Next ride’s start must be ≥ 3; ride 2 starts at 2 (invalid), but ride 3 starts at 4 (valid) so binary search finds ride 3.
    • dp[0] = max(dp[1], 4 + dp[2]) = max(9, 4 + 9) = 13.
• The maximum earnings are 13.

Complexity Analysis

• Time Complexity:
  • Sorting the rides takes O(m log m), where m is the number of rides.
  • For each ride, performing a binary search takes O(log m).
  • Overall, the DP step takes O(m log m).
• Space Complexity:
  • O(m) for the DP array and the auxiliary start times array.

Python Code