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

这道题到底在问什么

输入

n=5, rides=[[2,5,4],[1,5,1]]

输出

7 (接第 0 单,5 减 2 加 4 等于 7)

输入

n=20, rides=[[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]

输出

20 (接 3 单)

最优解：一步一步想明白

1. 3记住这套框架:排好序后,每一单都做一次「接还是不接」的取舍。不接就顺延,接就把本单收益加上从下一个不冲突订单往后的最优。下面把这张表一列一列、再一行一行填出来。
2. 4排序完成先把 6 个订单按起点从小到大排好,正好这组本来就是有序的。表格每一行是一个订单,左边两列是它的起点和终点。收益、下一单、还有最关键的 f 值三列先空着,等会儿一列一列补上。排序是后面二分找下一单的前提,一定要先做。
3. 5收益列填好补上收益这一列。每单收益等于终点减起点,再加它自己的小费。比如单0从 1 到 6 小费 1,收益就是 6 减 1 加 1 等于 6;单1从 3 到 10 小费 2,收益是 10 减 3 加 2 等于 9。六个订单的收益依次是 6、9、5、3、5、6。注意单1一个人就值 9,是这里最肥的一单。
4. 6下一单列填好再补下一单这一列。接了某单,车就开到了它的终点,下一个能接的必须是起点不早于这个终点的订单。因为已经按起点排好序,用二分就能很快找到第一个满足的。比如单0在 6 下客,起点不小于 6 的第一单是单2;单4在 15 下客,后面再没有起点到 15 的了,标一个无。允许下一单起点正好等于本单终点,因为同一地点可以先放下再接上。
5. 7f 值从后往前填开始填最右边的 f 值列。约定一个虚拟的末尾:如果一单都不接,盈利就是 0,记成 f 的第 6 格等于 0。填表从最后一单往前推,因为每一单的 f 都依赖它后面的格子,后面先算好,前面才有得取。下面从单5 开始,一单填一遍。
6. 8算单5 的不接轮到单5,起点 13,终点 18。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[末尾] = 0,也就是 0。这一项不花本单的收益,先把它记在心里。
7. 9算单5 的接再看第二种:接单5。先拿到它的收益 6,车开到终点 18,下一个能接的是 无,从那往后的最优是 f[末尾] = 0。两个加起来是 6 加 0 等于 6。它后面没有能接的单了,所以只加末尾的 0。
8. 10f[单5] = 6两种选择摆在一起,取较大的那个:不接是 0,接是 6,接更划算,所以单5 的 f 记成 6,这一步我们倾向接它。 把 6 填进 f 值列,继续往前推。
9. 11算单4 的不接轮到单4,起点 12,终点 15。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单5] = 6,也就是 6。这一项不花本单的收益,先把它记在心里。
10. 12算单4 的接再看第二种:接单4。先拿到它的收益 5,车开到终点 15,下一个能接的是 无,从那往后的最优是 f[末尾] = 0。两个加起来是 5 加 0 等于 5。它后面没有能接的单了,所以只加末尾的 0。
11. 13f[单4] = 6两种选择摆在一起,取较大的那个:不接是 6,接是 5,不接反而更高,所以单4 的 f 记成 6,这一单在最优里跳过。 把 6 填进 f 值列,继续往前推。
12. 14算单3 的不接轮到单3,起点 11,终点 12。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单4] = 6,也就是 6。这一项不花本单的收益,先把它记在心里。
13. 15算单3 的接再看第二种:接单3。先拿到它的收益 3,车开到终点 12,下一个能接的是 单4,从那往后的最优是 f[单4] = 6。两个加起来是 3 加 6 等于 9。注意接了本单只能跳到 单4,中间被占住的订单就接不了了。
14. 16f[单3] = 9两种选择摆在一起,取较大的那个:不接是 6,接是 9,接更划算,所以单3 的 f 记成 9,这一步我们倾向接它。 把 9 填进 f 值列,继续往前推。
15. 17算单2 的不接轮到单2,起点 10,终点 12。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单3] = 9,也就是 9。这一项不花本单的收益,先把它记在心里。
16. 18算单2 的接再看第二种:接单2。先拿到它的收益 5,车开到终点 12,下一个能接的是 单4,从那往后的最优是 f[单4] = 6。两个加起来是 5 加 6 等于 11。注意接了本单只能跳到 单4,中间被占住的订单就接不了了。
17. 19f[单2] = 11两种选择摆在一起,取较大的那个:不接是 9,接是 11,接更划算,所以单2 的 f 记成 11,这一步我们倾向接它。 把 11 填进 f 值列,继续往前推。
18. 20算单1 的不接轮到单1,起点 3,终点 10。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单2] = 11,也就是 11。这一项不花本单的收益,先把它记在心里。
19. 21算单1 的接再看第二种:接单1。先拿到它的收益 9,车开到终点 10,下一个能接的是 单2,从那往后的最优是 f[单2] = 11。两个加起来是 9 加 11 等于 20。注意接了本单只能跳到 单2,中间被占住的订单就接不了了。
20. 22f[单1] = 20两种选择摆在一起,取较大的那个:不接是 11,接是 20,接更划算,所以单1 的 f 记成 20,这一步我们倾向接它。 把 20 填进 f 值列,继续往前推。
21. 23算单0 的不接轮到单0,起点 1,终点 6。先看第一种选择:不接它。不接就等于从下一单往后随便挑,盈利直接沿用 f[单1] = 20,也就是 20。这一项不花本单的收益,先把它记在心里。
22. 24算单0 的接再看第二种:接单0。先拿到它的收益 6,车开到终点 6,下一个能接的是 单2,从那往后的最优是 f[单2] = 11。两个加起来是 6 加 11 等于 17。注意接了本单只能跳到 单2,中间被占住的订单就接不了了。
23. 25f[单0] = 20两种选择摆在一起,取较大的那个:不接是 20,接是 17,不接反而更高,所以单0 的 f 记成 20,这一单在最优里跳过。 把 20 填进 f 值列,继续往前推。
24. 26答案 = 20f 值列填满,f[单0] 等于 20,就是答案。顺着每一步的取舍回放:最优方案是接 单1、单2、单5,收益 9 加 5 加 6 合起来正好 20。这三单首尾相接又不冲突:单1到 10 下客,单2从 10 上客,单2到 12,再等到单5从 13 上客。见单就接反而会被便宜的短单占住路段,取 max 才躲开了这个坑。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

#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);
    }
};

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;
    }
}

复杂度

面试官可能追问