出租车的最大盈利 图解题解

一条单行道上挑单，到底在赚什么钱

一条路上有 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 存不下。排序也省不得，乱序上二分出的『下一单』是错位的。

Python

from __future__ import annotations
from 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)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        sort(rides.begin(), rides.end());
        int m = rides.size();
        long long f[m];
        memset(f, -1, sizeof(f));
        function<long long(int)> dfs = [&](int i) -> long long {
            if (i >= m) {
                return 0;
            }
            if (f[i] != -1) {
                return f[i];
            }
            auto& r = rides[i];
            int st = r[0], ed = r[1], tip = r[2];
            int j = lower_bound(rides.begin() + i + 1, rides.end(), ed, [](auto& a, int val) { return a[0] < val; }) - rides.begin();
            return f[i] = max(dfs(i + 1), dfs(j) + ed - st + tip);
        };
        return dfs(0);
    }
};

Java

import java.util.*;
class Solution {
    private int m;
    private int[][] rides;
    private Long[] f;

    public long maxTaxiEarnings(int n, int[][] rides) {
        Arrays.sort(rides, (a, b) -> a[0] - b[0]);
        m = rides.length;
        f = new Long[m];
        this.rides = rides;
        return dfs(0);
    }

    private long dfs(int i) {
        if (i >= m) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        int[] r = rides[i];
        int st = r[0], ed = r[1], tip = r[2];
        int j = search(ed, i + 1);
        return f[i] = Math.max(dfs(i + 1), dfs(j) + ed - st + tip);
    }

    private int search(int x, int l) {
        int r = m;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (rides[mid][0] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}