Company: Wells_Frago_IIT_kgp
Difficulty: medium
Taxi Driver Problem Description A taxi driver knows the pick-up and drop-off locations of people requesting services. All locations are measured in km from the starting point (0 km). For each km traveled, the driver charges 1 unit of money per passenger. Additionally, some passengers are willing to pay an extra tip. Notes: The taxi can accommodate only one passenger at a time. The driver cannot backtrack. If a passenger is picked up at location 2 and dropped off at location 9, the driver cannot accommodate a passenger at locations 3 through 8. If there are two people and their locations overlap, only one of them can be accepted. Determine the maximum amount the driver can earn. Examples Example 1: Input: pickup = [0, 2, 9, 10, 11, 12] drop = [5, 9, 11, 14, 17] tip = [1, 2, 3, 2, 2, 1] Explanation: The optimal way to earn the most money is by accepting passengers at indices 1, 2, and 5: Passenger at index 1: 9 - 2 + 2 = 9 (distance + tip) Passenger at index 2: 11 - 9 + 3 = 5 Passenger a