题目描述
思路解析
一句话答案：LeetCode 2008 出租车的最大盈利：订单按起点排序，f[i] 记从第 i 单往后最多赚多少，每单在不接沿用与接单赚 end−start+tip 再二分跳去下一单之间取大，即带权区间调度，时间 O(m log m)、空间 O(m)。
一条单行道上挑单，到底在赚什么钱
一条路上有 n 个地点，出租车只能往编号大的方向开，不能回头。每位乘客是一单 rides[i]=[start,end,tip]，接了能赚 end−start+tip；同一时刻只能载一位，可以在同一地点放下一位、马上接上另一位。要挑一批互不冲突的订单，让总盈利最大。
见单就接为什么会亏，全枚举为什么试不完
m 个订单每单接或不接，2 的 m 次方种组合，几万条试不完。贪心（每步只拿眼前最赚的）靠不住：题面 n=20 那组，值 9 那单最赚先接，车到 10，再接只剩值 6 的末单，9+6=15；先接 1 到 6 的头单，车占到 6、值 9 错过，连头单最多 6+5+6=17（加 10 到 12、13 到 18），都不到最优的 20。
f[i] 定成从第 i 单往后，两条路才有得比
先把订单按起点从小到大排序，『往后』才有方向。这题用动态规划（简称 DP，把『从某单往后最多赚多少』这类会反复被问的小问题各算一次、存表复用）。状态（表里每格记的数）定成 f[i]：从排序后第 i 单起往后随便挑，最多能赚多少。答案是 f[0]。
接了这单，为什么要用二分找下一单
填 f[i] 摆两条路取大。不接：这单当不存在，沿用 f[i+1]。接：落袋 end−start+tip，车到 end 才空出来，下一个能接的是起点不小于 end 的第一单，记作第 j 单，再加 f[j]。订单已按起点排好序，第 j 单用二分（每次砍一半范围去定位）就能找到，参考代码里 bisect_left 干的就是这事。『不小于』含等号：同一地点放人再接人不算冲突。
转移式（由后面的格子推出当前格的式子）就是 f[i]=max(f[i+1], end−start+tip+f[j])。做过 LeetCode 1235 规划兼职工作会眼熟，这题是它搬上数轴的出租车版。
六单从后往前，f 是怎么涨到 20 的
题面第二组：n=20，rides=[[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]，按起点排好记作单0 到单5。各单收益是终点减起点加小费，依次 6、9、5、3、5、6；接完能跳到的下一单依次是单2、单2、单4、单4、无、无。
倒着填：单5 接得 6，不接是 0，f 记 6；单4 接只有 5，不如沿用单5 的 6；单3 接是 3+6=9，胜过 6；单2 接是 5+6=11，胜过 9；单1 接是 9+11=20，胜过不接的 11；单0 接是 6+11=17，输给不接的 20。f[0]=20 就是答案：接单1、单2、单5，9+5+6=20。
二分把等号写丢，20 为什么缩成 18
排序 O(m log m)（大 O 衡量规模对计算量的放大倍数），每单一次二分 log m，总时间 O(m log m)；存 f 的表是 O(m)。找下一单写成严格大于终点，10 下客、10 上客这种首尾相接就被误判冲突，上面那组的 20 当场缩成 18。总盈利能累到几十亿，Java 和 C++ 得用长整型接住，int 存不下。排序也省不得，乱序上二分出的『下一单』是错位的。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套框架:排好序后,每一单都做一次「接还是不接」的取舍。不接就顺延,接就把本单收益加上从下一个不冲突订单往后的最优。下面把这张表一列一列、再一行一行填出来。
第一步 · 按起点排序,列出 6 个订单：先把 6 个订单按起点从小到大排好,正好这组本来就是有序的。表格每一行是一个订单,左边两列是它的起点和终点。收益、下一单、还有最关键的 f 值三列先空着,等会儿一列一列补上。排序是后面二分找下一单的前提,一定要先做。
第二步 · 算每单收益 = 终点 减 起点 加 小费：补上收益这一列。每单收益等于终点减起点,再加它自己的小费。比如单0从 1 到 6 小费 1,收益就是 6 减 1 加 1 等于 6;单1从 3 到 10 小费 2,收益是 10 减 3 加 2 等于 9。六个订单的收益依次是 6、9、5、3、5、6。注意单1一个人就值 9,是这里最肥的一单。
第三步 · 二分找每单的下一单(起点 ≥ 本单终点)：再补下一单这一列。接了某单,车就开到了它的终点,下一个能接的必须是起点不早于这个终点的订单。因为已经按起点排好序,用二分就能很快找到第一个满足的。比如单0在 6 下客,起点不小于 6 的第一单是单2;单4在 15 下客,后面再没有起点到 15 的了,标一个无。允许下一单起点正好等于本单终点,因为同一地点可以先放下再接上。
起手 · 虚拟末尾 f 等于 0,从最后一单往前填：开始填最右边的 f 值列。约定一个虚拟的末尾:如果一单都不接,盈利就是 0,记成 f 的第 6 格等于 0。填表从最后一单往前推,因为每一单的 f 都依赖它后面的格子,后面先算好,前面才有得取。下面从单5 开始,一单填一遍。
单5 · 选项一:不接,盈利顺延：轮到单5,起点 13,终点 18。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[末尾] = 0,也就是 0。这一项不花本单的收益,先把它记在心里。
单5 · 选项二:接,收益 6 加下一单最优：再看第二种:接单5。先拿到它的收益 6,车开到终点 18,下一个能接的是 无,从那往后的最优是 f[末尾] = 0。两个加起来是 6 加 0 等于 6。它后面没有能接的单了,所以只加末尾的 0。
单5 · 结算:两者取较大,f = 6：两种选择摆在一起,取较大的那个:不接是 0,接是 6,接更划算,所以单5 的 f 记成 6,这一步我们倾向接它。 把 6 填进 f 值列,继续往前推。
单4 · 选项一:不接,盈利顺延：轮到单4,起点 12,终点 15。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单5] = 6,也就是 6。这一项不花本单的收益,先把它记在心里。
单4 · 选项二:接,收益 5 加下一单最优：再看第二种:接单4。先拿到它的收益 5,车开到终点 15,下一个能接的是 无,从那往后的最优是 f[末尾] = 0。两个加起来是 5 加 0 等于 5。它后面没有能接的单了,所以只加末尾的 0。
单4 · 结算:两者取较大,f = 6：两种选择摆在一起,取较大的那个:不接是 6,接是 5,不接反而更高,所以单4 的 f 记成 6,这一单在最优里跳过。 把 6 填进 f 值列,继续往前推。
单3 · 选项一:不接,盈利顺延：轮到单3,起点 11,终点 12。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单4] = 6,也就是 6。这一项不花本单的收益,先把它记在心里。
单3 · 选项二:接,收益 3 加下一单最优：再看第二种:接单3。先拿到它的收益 3,车开到终点 12,下一个能接的是 单4,从那往后的最优是 f[单4] = 6。两个加起来是 3 加 6 等于 9。注意接了本单只能跳到 单4,中间被占住的订单就接不了了。
单3 · 结算:两者取较大,f = 9：两种选择摆在一起,取较大的那个:不接是 6,接是 9,接更划算,所以单3 的 f 记成 9,这一步我们倾向接它。 把 9 填进 f 值列,继续往前推。
单2 · 选项一:不接,盈利顺延：轮到单2,起点 10,终点 12。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单3] = 9,也就是 9。这一项不花本单的收益,先把它记在心里。
单2 · 选项二:接,收益 5 加下一单最优：再看第二种:接单2。先拿到它的收益 5,车开到终点 12,下一个能接的是 单4,从那往后的最优是 f[单4] = 6。两个加起来是 5 加 6 等于 11。注意接了本单只能跳到 单4,中间被占住的订单就接不了了。
单2 · 结算:两者取较大,f = 11：两种选择摆在一起,取较大的那个:不接是 9,接是 11,接更划算,所以单2 的 f 记成 11,这一步我们倾向接它。 把 11 填进 f 值列,继续往前推。
单1 · 选项一:不接,盈利顺延：轮到单1,起点 3,终点 10。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单2] = 11,也就是 11。这一项不花本单的收益,先把它记在心里。
单1 · 选项二:接,收益 9 加下一单最优：再看第二种:接单1。先拿到它的收益 9,车开到终点 10,下一个能接的是 单2,从那往后的最优是 f[单2] = 11。两个加起来是 9 加 11 等于 20。注意接了本单只能跳到 单2,中间被占住的订单就接不了了。
单1 · 结算:两者取较大,f = 20：两种选择摆在一起,取较大的那个:不接是 11,接是 20,接更划算,所以单1 的 f 记成 20,这一步我们倾向接它。 把 20 填进 f 值列,继续往前推。
单0 · 选项一:不接,盈利顺延：轮到单0,起点 1,终点 6。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单1] = 20,也就是 20。这一项不花本单的收益,先把它记在心里。
单0 · 选项二:接,收益 6 加下一单最优：再看第二种:接单0。先拿到它的收益 6,车开到终点 6,下一个能接的是 单2,从那往后的最优是 f[单2] = 11。两个加起来是 6 加 11 等于 17。注意接了本单只能跳到 单2,中间被占住的订单就接不了了。
单0 · 结算:两者取较大,f = 20：两种选择摆在一起,取较大的那个:不接是 20,接是 17,不接反而更高,所以单0 的 f 记成 20,这一单在最优里跳过。 把 20 填进 f 值列,继续往前推。
回放 · 最优接单 单1、单2、单5,答案 20：f 值列填满,f[单0] 等于 20,就是答案。顺着每一步的取舍回放:最优方案是接 单1、单2、单5,收益 9 加 5 加 6 合起来正好 20。这三单首尾相接又不冲突:单1到 10 下客,单2从 10 上客,单2到 12,再等到单5从 13 上客。见单就接反而会被便宜的短单占住路段,取 max 才躲开了这个坑。
边界想清:单个订单直接算收益、两单重叠取较大、首尾相接的两单起点等于终点可以都接。
面试重点:排序后 f[i] 取接与不接的较大、靠二分找下一单、也可换成按地点的 O(n 加 m) DP。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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)复杂度
- 时间：O(m log m)，m 是订单数。排序是 m log m;之后每个订单状态只算一次,算的时候用二分找下一单是 log m,合起来还是 m log m 级别。用前缀式的位置 DP 也能做到接近线性,这里按参考解的排序加二分算
- 空间：O(m)，按峰值算。备忘录数组 f 是 m 个格子;自顶向下递归时调用栈最深也是订单个数量级。两者都是 O(m),不额外开与地点数 n 相关的大表
易错点
面试追问把动画讲成自己的话
追问这题的状态和转移怎么定义?
追问为什么要排序,还要二分?
追问还有别的解法吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
两个最好的不重叠活动
LeetCode 2054 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题