Medium

题目描述

在你驾驶出租车的道路上有 n 个点。道路上的 n 个点按你前进的方向从 1 到 n 标记，你想要从点 1 开始驾驶到点 n，通过接送乘客来赚钱。你不能改变出租车的行驶方向。

乘客用一个下标从 0 开始的二维整数数组 rides 表示，其中 rides[i] = [starti, endi, tipi] 表示第 i 个乘客请求从点 starti 到点 endi 的行程，并愿意支付 tipi 元的小费。

对于你接送的每个乘客 i，你可以赚取 endi - starti + tipi 元。你每次最多只能接送一个乘客。

给你 n 和 rides，请返回你通过最优接送乘客能赚取的最多金额。

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

示例 1：

输入：n = 5, rides = [[2,5,4],[1,5,1]]
输出：7
解释：我们可以接送乘客 0，赚取 5 - 2 + 4 = 7 元。

示例 2：

输入：n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
输出：20
解释：我们接送以下乘客：
- 接送乘客 1 从点 3 到点 10，赚取 10 - 3 + 2 = 9 元。
- 接送乘客 2 从点 10 到点 12，赚取 12 - 10 + 3 = 5 元。
- 接送乘客 5 从点 13 到点 18，赚取 18 - 13 + 1 = 6 元。
总共赚取 9 + 5 + 6 = 20 元。

约束条件：

  • 1 <= n <= 10^5
  • 1 <= rides.length <= 3 * 10^4
  • rides[i].length == 3
  • 1 <= starti < endi <= n
  • 1 <= tipi <= 10^5

解题思路

这道题是一个经典的区间调度动态规划问题。

解题思路：

  1. 首先按照乘客的结束位置对所有行程进行排序，这样可以确保状态转移的顺序性
  2. 定义状态：dp[i] 表示考虑前 i 个行程能获得的最大收益
  3. 对于第 i 个行程，有两种选择：
    • 不接这个乘客：dp[i] = dp[i-1]
    • 接这个乘客：需要找到上一个不冲突的行程位置 j，使得 dp[i] = dp[j] + profit[i]

关键优化： 由于行程按结束位置排序，当前行程的开始位置与之前某个行程的结束位置进行比较时，可以使用二分查找快速找到最大的不冲突位置，时间复杂度从 O(n) 降到 O(log n)。

具体步骤：

  1. 将所有行程按结束位置排序
  2. 对每个行程计算收益：end - start + tip
  3. 使用动态规划，结合二分查找优化状态转移
  4. 返回 dp[rides.length] 作为最终答案

这种方法时间复杂度为 O(m log m)，其中 m 是行程数量，空间复杂度为 O(m)。

代码实现

class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        // 按结束位置排序
        sort(rides.begin(), rides.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        
        int m = rides.size();
        vector<long long> dp(m + 1, 0);
        
        for (int i = 0; i < m; i++) {
            int start = rides[i][0], end = rides[i][1], tip = rides[i][2];
            long long profit = end - start + tip;
            
            // 二分查找最大的不冲突位置
            int left = 0, right = i;
            while (left < right) {
                int mid = (left + right + 1) / 2;
                if (rides[mid - 1][1] <= start) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            
            dp[i + 1] = max(dp[i], dp[left] + profit);
        }
        
        return dp[m];
    }
};

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        # 按结束位置排序
        rides.sort(key=lambda x: x[1])
        
        m = len(rides)
        dp = [0] * (m + 1)
        
        for i in range(m):
            start, end, tip = rides[i]
            profit = end - start + tip
            
            # 二分查找最大的不冲突位置
            left, right = 0, i
            while left < right:
                mid = (left + right + 1) // 2
                if rides[mid - 1][1] <= start:
                    left = mid
                else:
                    right = mid - 1
            
            dp[i + 1] = max(dp[i], dp[left] + profit)
        
        return dp[m]

public class Solution {
    public long MaxTaxiEarnings(int n, int[][] rides) {
        // 按结束位置排序
        Array.Sort(rides, (a, b) => a[1].CompareTo(b[1]));
        
        int m = rides.Length;
        long[] dp = new long[m + 1];
        
        for (int i = 0; i < m; i++) {
            int start = rides[i][0], end = rides[i][1], tip = rides[i][2];
            long profit = end - start + tip;
            
            // 二分查找最大的不冲突位置
            int left = 0, right = i;
            while (left < right) {
                int mid = (left + right + 1) / 2;
                if (rides[mid - 1][1] <= start) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            
            dp[i + 1] = Math.Max(dp[i], dp[left] + profit);
        }
        
        return dp[m];
    }
}

var maxTaxiEarnings = function(n, rides) {
    // 按结束位置排序
    rides.sort((a, b) => a[1] - b[1]);
    
    const m = rides.length;
    const dp = new Array(m + 1).fill(0);
    
    for (let i = 0; i < m; i++) {
        const [start, end, tip] = rides[i];
        const profit = end - start + tip;
        
        // 二分查找最大的不冲突位置
        let left = 0, right = i;
        while (left < right) {
            const mid = Math.floor((left + right + 1) / 2);
            if (rides[mid - 1][1] <= start) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        dp[i + 1] = Math.max(dp[i], dp[left] + profit);
    }
    
    return dp[m];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m log m)
空间复杂度O(m)

其中 m 为 rides 数组的长度。排序需要 O(m log m)，动态规划过程中每次二分查找需要 O(log m)，总共进行 m 次，所以总时间复杂度为 O(m log m)。空间复杂度主要用于存储 dp 数组。

相关题目