2023-12-08每日一题

一、题目编号

2008. 出租车的最大盈利

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

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

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

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

示例 1：

示例 2：

提示：

• 1 <= n <= 10⁵
• 1 <= rides.length <= 3 * 10⁴
• rides[i].length == 3
• 1 <= starti < endi <= n
• 1 <= tipi <= 10⁵

四、解题代码

class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        sort(rides.begin(), rides.end(), [&](const vector<int> &r1, const vector<int> &r2) -> bool {
            return r1[1] < r2[1];
        });
        int m = rides.size();
        vector<long long> dp(m + 1);
        for (int i = 0; i < m; i++) {
            int j = upper_bound(rides.begin(), rides.begin() + i, rides[i][0], [](int x, const vector<int> &r) -> bool {
                return x < r[1];
            }) - rides.begin();
            dp[i + 1] = max(dp[i], dp[j] + rides[i][1] - rides[i][0] + rides[i][2]);
        }
        return dp[m];
    }
};

五、解题思路

(1) 动态规划+二分查找