2008.出租车的最大盈利

链接：2008.出租车的最大盈利
难度：Medium
标签：数组、哈希表、二分查找、动态规划、排序
简介：给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。

题解 1 - python

• 编辑时间：2023-12-08
• 执行用时：700ms
• 内存消耗：31.9MB
• 编程语言：python
• 解法介绍：二分+动态规划记录当前点的最大值。

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort(key = lambda o: (o[1], o[0], o[2]))
        dp = [0] * (len(rides) + 1)
        for i in range(len(rides)):
            start, end, tip = rides[i]
            l = -1
            r = i - 1
            while l < r:
                m = (l + r + 1) // 2
                if rides[m][1] <= start: l = m
                else: r = m - 1
            dp[i + 1] = max(dp[i], dp[l + 1] + end - start + tip)
        return dp[-1]