[
dp
binary search
sort
]
Leetcode 2008. Maximum Earnings From Taxi
Problem statement
https://leetcode.com/problems/maximum-earnings-from-taxi/
Solution
This problem is very similar to problem 1235. Maximum Profit in Job Scheduling. The only difference is what profit we have given our ride: it is calculated as rides[k][2] - rides[k][0] + rides[k][1]
.
Complexity
It is O(m log m)
, where m = len(rides)
.
Code
import bisect
class Solution:
def maxTaxiEarnings(self, n, rides):
rides = sorted(rides)
S = [i[0] for i in rides]
m = len(rides)
dp = [0]*(m+1)
for k in range(m-1, -1, -1):
temp = bisect_left(S, rides[k][1])
dp[k] = max(dp[k+1], rides[k][2] - rides[k][0] + rides[k][1] + dp[temp])
return dp[0]
If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!