# 2008. 出租车的最大盈利
### 题目地址(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：
输入：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 * 104
rides[i].length == 3
1 <= starti < endi <= n
1 <= tipi <= 105
```
### 前置知识
* 动态规划
* 二分
### 公司
* 暂无
### 思路
这是一个典型的最长上升子序列（LIS）问题。如果你对最长上升子序列不熟悉，强烈建议先看一下我之前写的专题：
LIS 问题的常规做法是 $n^2$ ， 而这道题的数据范围是 $10^5$， 这意味着我们使用平方的解法是无法通过的。关于这点不明白的可以看下我之前写的文章：
我们可以用动态规划来解， dp\[i] 表示仅考虑 rides 0 到 i （左右闭合区间），所能挣的最多的钱。因此 dp\[len(rides)-1] 就是答案。
那么状态如何转移呢？传统的 LIS 问题，对于每一个 j 我们都向前找到第一个满足 rides\[j]\[0] >= rides\[i]\[1] 的 i，我们需要两层循环枚举所有可能。那么如何优化呢？
实际上前面的文章也提到过，这里再次强调一下。由于我们需要**向前找到第一个满足 rides\[j]\[0] >= rides\[i]\[1] 的 i**，那么我们可以先对结束时间排序，接下来二分找到**最右满足条件的 i**，这样时间复杂度可以降低到 $nlogn$。 由于这是一个典型的最右满足条件的二分，我们直接使用模板解决。不熟悉二分的可以看下我的二分专题：
> 由于我们是找满足条件的 dp\[i]\[1] ，因此需要对结束时间而不是开始时间排序
### 关键点
* 二分优化时间复杂度
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
rides.sort(key=lambda x:x[1])
n = len(rides)
dp = [e-s+t for s,e,t in rides]
def bisect_right(rides, i):
l, r = 0, i
while l <= r:
mid = (l+r)//2
if rides[i][0] >= rides[mid][1]:
l = mid + 1
else:
r = mid - 1
return r
for j in range(1, n):
i = bisect_right(rides, j)
if i == -1:
dp[j] = max(dp[j], dp[j-1])
else:
dp[j] = max(dp[j], dp[j-1], dp[i] + rides[j][1] - rides[j][0] + rides[j][2])
return max(dp)
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(nlogn)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/2008.maximum-earnings-from-taxi.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.