题目描述
思路解析动画文字版
记住这套框架:排好序后,每一单都做一次「接还是不接」的取舍。不接就顺延,接就把本单收益加上从下一个不冲突订单往后的最优。下面把这张表一列一列、再一行一行填出来。
第一步 · 按起点排序,列出 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题