What is the primary approach for solving the Maximum Earnings From Taxi problem?

The problem can be solved using a combination of sorting, dynamic programming, and hash table lookups to efficiently track maximum earnings.

How does dynamic programming help in this problem?

Dynamic programming is used to keep track of the maximum earnings at each point, considering the rides picked up and ensuring that they don't overlap.

Can sorting the rides by their ending points improve the solution?

Yes, sorting the rides by their ending points allows for efficient comparison and helps avoid overlapping rides while optimizing earnings.

Why is hash table lookup important in this problem?

Hash table lookup helps in quickly retrieving the maximum earnings up to a specific point in the ride sequence, enabling efficient dynamic programming.

What are the potential variants of the Maximum Earnings From Taxi problem?

Variants include handling a larger number of rides, imposing additional constraints on ride lengths or tips, or allowing multiple passengers per trip.

#2008

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

出租车的最大盈利

你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [start i , end i…

数组哈希表二分查找动态规划排序

题目描述

你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。

乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [start_i, end_i, tip_i] 表示第 i 位乘客需要从地点 start_i 前往 end_i ，愿意支付 tip_i 元的小费。

每一位 你选择接单的乘客 i ，你可以盈利 end_i - start_i + tip_i 元。你同时最多只能接一个订单。

给你 n 和 rides ，请你返回在最优接单方案下，你能盈利最多多少元。

注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。

示例 1：

输入：n = 5, rides = [[2,5,4],[1,5,1]]
输出：7
解释：我们可以接乘客 0 的订单，获得 5 - 2 + 4 = 7 元。

示例 2：

输入：n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
输出：20
解释：我们可以接以下乘客的订单：
- 将乘客 1 从地点 3 送往地点 10 ，获得 10 - 3 + 2 = 9 元。
- 将乘客 2 从地点 10 送往地点 12 ，获得 12 - 10 + 3 = 5 元。
- 将乘客 5 从地点 13 送往地点 18 ，获得 18 - 13 + 1 = 6 元。
我们总共获得 9 + 5 + 6 = 20 元。

提示：

1 <= n <= 10⁵
1 <= rides.length <= 3 * 10⁴
rides[i].length == 3
1 <= start_i < end_i <= n
1 <= tip_i <= 10⁵

lightbulb

解题思路

方法一：记忆化搜索 + 二分查找

我们先将 $rides$ 按照 $start$ 从小到大排序，然后设计一个函数 $dfs(i)$ ，表示从第 $i$ 个乘客开始接单，最多能获得的小费。答案即为 $dfs(0)$ 。

函数 $dfs(i)$ 的计算过程如下：

对于第 $i$ 个乘客，我们可以选择接单，也可以选择不接单。如果不接单，那么最多能获得的小费为 $dfs(i + 1)$ ；如果接单，那么我们可以通过二分查找，找到在第 $i$ 个乘客下车地点之后遇到的第一个乘客，记为 $j$ ，那么最多能获得的小费为 $dfs(j) + end_i - start_i + tip_i$ 。取两者的较大值即可。即：

dfs(i) = \max(dfs(i + 1), dfs(j) + end_i - start_i + tip_i)

其中 $j$ 是满足 $start_j \ge end_i$ 的最小的下标，可以通过二分查找得到。

此过程中，我们可以使用记忆化搜索，将每个状态的答案保存下来，避免重复计算。

时间复杂度 $O(m \times \log m)$ ，空间复杂度 $O(m)$ 。其中 $m$ 为 $rides$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(rides):
                return 0
            st, ed, tip = rides[i]
            j = bisect_left(rides, ed, lo=i + 1, key=lambda x: x[0])
            return max(dfs(i + 1), dfs(j) + ed - st + tip)

        rides.sort()
        return dfs(0)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding dynamic programming and hash table usage for optimized solutions.
question_mark
Ability to identify and implement efficient algorithms for overlapping interval problems.
question_mark
Proficiency with greedy algorithms for selecting non-overlapping tasks.

warning

常见陷阱

外企场景

error
Forgetting to check for ride overlap or choosing an incorrect ride combination.
error
Not optimizing the solution by sorting rides before applying dynamic programming.
error
Misunderstanding the interaction between dynamic programming and hash table lookups.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increased number of rides to test performance optimization.
arrow_right_alt
Introducing additional constraints on maximum ride length or tips.
arrow_right_alt
Allowing multiple passengers at a time to drive, increasing complexity.

help

常见问题

外企场景

继续练习

#2501 数组中最长的方波 #2713 矩阵中严格递增的单元格数 #2830 销售利润最大化