#2008
Maximum Earnings From Taxi
specialist · 920 · lc medium +32 · verified · 46.3% accepted · 1,409 likes · top 30%
Description
A taxi drives along a road with n points (labeled 1 to n). Passengers are described by rides[i] = [start, end, tip]: picking up passenger i earns end - start + tip dollars. Only one passenger may be carried at a time, and passengers may be exchanged at the same point. Return the maximum earnings achievable driving from point 1 to point n.
Example 1:
Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7
Explanation: We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.
Example 2:
Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20
Explanation: We will pick up the following passengers:
- Drive passenger 1 from point 3 to point 10 for a profit of 10 - 3 + 2 = 9 dollars.
- Drive passenger 2 from point 10 to point 12 for a profit of 12 - 10 + 3 = 5 dollars.
- Drive passenger 5 from point 13 to point 18 for a profit of 18 - 13 + 1 = 6 dollars.
We earn 9 + 5 + 6 = 20 dollars in total.
Code
1
2
3