LC-2008 Medium LeetCode

2008. Maximum Earnings From Taxi

Array Hash Table Binary Search Dynamic Programming Sorting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 45% Topics: Array, Hash Table, Binary Search, Dynamic Programming, Sorting

Reading material

Arrays & Hashing 12 min Binary Search 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n + mlogm), m is the number of rides
# Space: O(n)

class Solution(object):
    def maxTaxiEarnings(self, n, rides):
        """
        :type n: int
        :type rides: List[List[int]]
        :rtype: int
        """
        rides.sort()
        dp = [0]*(n+1)
        j = 0
        for i in xrange(1, n+1):
            dp[i] = max(dp[i], dp[i-1])
            while j < len(rides) and rides[j][0] == i:
                dp[rides[j][1]] = max(dp[rides[j][1]], dp[i]+rides[j][1]-rides[j][0]+rides[j][2])
                j += 1
        return dp[-1]

Solution from kamyu104/LeetCode-Solutions · MIT