Maximum Earnings From Taxi

Maximum Earnings From Taxi

1. What is this problem about?

Maximum Earnings From Taxi is a optimization problem where you act as a taxi driver. You have a set of ride requests, each with a start point, an end point, and a tip. The earnings for a ride are (end - start + tip). You can only take one ride at a time and must finish a ride before starting another (end_i <= start_j). The goal is to maximize your total earnings. This is a classic 'Weighted Interval Scheduling' problem.

2. Why is this asked in interviews?

This Maximum Earnings From Taxi interview question is a favorite for companies like Uber and Salesforce because it mirrors real-world resource allocation. It tests Dynamic Programming (DP) and Binary Search skills. Candidates must demonstrate they can build a solution where the choice to take a ride depends on the best possible earnings they could have made before that ride started.

3. Algorithmic pattern used

The problem utilizes Dynamic Programming combined with Sorting and Binary Search. First, you sort the rides by their end times. Then, you define a DP state where dp[i] represents the maximum earnings possible using a subset of the first i rides. For each ride, you have two choices: skip it (earning dp[i-1]) or take it. If you take it, your earnings are (ride_profit + dp[j]), where j is the index of the last ride that ended before the current ride started. Binary search is used to find index j quickly.

4. Example explanation

Rides: A: [1, 4, 4] -> Profit: (4-1+4) = 7 B: [2, 5, 2] -> Profit: (5-2+2) = 5 C: [5, 8, 1] -> Profit: (8-5+1) = 4

• Sort by end time: A(4), B(5), C(8).
• dp[0] = 0
• Ride A (ends 4): Max(skip=0, take=7+dp[none]) = 7. dp[4] = 7.
• Ride B (ends 5): Max(skip=dp[4], take=5+dp[last ride ending <= 2]) = Max(7, 5+0) = 7. dp[5] = 7.
• Ride C (ends 8): Max(skip=dp[5], take=4+dp[last ride ending <= 5]) = Max(7, 4+dp[5]) = Max(7, 4+7) = 11. dp[8] = 11. Max earnings = 11.

5. Common mistakes candidates make

A major pitfall is not sorting the rides, which makes it impossible to build the DP table correctly. Another is using a linear search to find the previous compatible ride, which results in O(n²) complexity—too slow for the constraints. Many also struggle with the off-by-one errors when implementing binary search on end times.

6. Interview preparation tip

Master the 'Select or Skip' DP pattern. It's the foundation for many optimization problems. When you see intervals or schedules with values, immediately think about sorting by end time and using DP with binary search.