Medium

Maximum Earnings From Taxi

LAB

Given rides [start,end,tip], return the maximum earnings from non-overlapping rides.

EXAMPLES

Example 1

Input
{
  "n": 5,
  "rides": [
    [
      2,
      5,
      4
    ],
    [
      1,
      5,
      1
    ]
  ]
}

Output
7

FUNCTION SHAPE

n: intrides: intMatrix→int

SOLUTION NOTE

Identical structure to job scheduling. Sort rides, use binary search to find next available ride after current ends.

Reveal reference solution +

pythonREFERENCE

def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
    rides.sort()

    @cache
    def dp(i):
        if i >= len(rides): return 0
        start, end, tip = rides[i]
        earn = end - start + tip
        next_idx = bisect_left(rides, (end,), key=lambda x: x[0])
        return max(earn + dp(next_idx), dp(i + 1))

    return dp(0)

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗