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!