class Solution {
public:
long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
}
};
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 <= 1051 <= rides.length <= 3 * 104rides[i].length == 31 <= starti < endi <= n1 <= tipi <= 105原站题解
rust 解法, 执行用时: 64 ms, 内存消耗: 5.4 MB, 提交时间: 2023-12-08 00:02:59
impl Solution {
pub fn max_taxi_earnings(n: i32,mut rides: Vec<Vec<i32>>) -> i64 {
rides.sort_by_key(|x|x[1]);
let mut n=n as usize;
let mut dp=vec![0;n+1];
let mut ride_index=0;
let mut end=0;
for ride in rides{
for i in end..=ride[1] as usize{
dp[i]=dp[end];
}
end=ride[1] as usize;
dp[end]=dp[end].max(dp[ride[0] as usize]+ride[1] as i64-ride[0] as i64+ride[2] as i64);
}
dp[end] as i64
}
}
javascript 解法, 执行用时: 240 ms, 内存消耗: 66.8 MB, 提交时间: 2023-12-08 00:02:11
/**
* @param {number} n
* @param {number[][]} rides
* @return {number}
*/
var maxTaxiEarnings = function(n, rides) {
rides = rides.sort((a,b) => a[1] - b[1]);
let dp = new Array(n + 1).fill(0);
let index = 0;
dp[0] = 0;
for (let i = 1; i < dp.length; i++) {
dp[i] = dp[i - 1];
while ((index < rides.length) && (i == rides[index][1])) {
dp[i] = Math.max((dp[rides[index][0]] + rides[index][1] - rides[index][0] + rides[index][2]), dp[i - 1], dp[i]);
index ++;
}
}
return dp[dp.length - 1];
};
python3 解法, 执行用时: 504 ms, 内存消耗: 27.3 MB, 提交时间: 2023-09-17 12:00:42
class Solution:
def maxTaxiEarnings(self, n, rides):
heapq.heapify(rides)
nums = [0] * (n + 1)
ret = 0
for i, j in enumerate(nums):
ret = max(ret, j)
while rides and i == rides[0][0]:
l, r, t = heapq.heappop(rides)
nums[r] = max(nums[r], ret + r - l + t)
return ret
# dp
def maxTaxiEarnings2(self, n: int, rides: List[List[int]]) -> int:
end_start_tip = collections.defaultdict(list)
for start, end, tip in rides:
start -= 1
end -= 1
end_start_tip[end].append((start, end - start + tip))
dp = [0 for _ in range(n)]
for i in range(1, n):
dp[i] = max(dp[i], dp[i - 1])
for ss, tt in end_start_tip[i]:
dp[i] = max(dp[i], dp[ss] + tt)
return dp[n - 1]
# dp + 二分
def maxTaxiEarnings3(self, n: int, rides: List[List[int]]) -> int:
rn = len(rides)
rides.sort(key = lambda x: x[1])
dp = [0 for _ in range(rn)]
for i in range(rn):
#--------当前可获得的利润
cur = rides[i][1] - rides[i][0] + rides[i][2]
#--------若是接当前的单
#--二分-最右
l = -1
r = i - 1
while l < r:
mid = (l + r + 1) // 2
if rides[mid][1] <= rides[i][0]:
l = mid
else:
r = mid - 1
if 0 <= l:
cur += dp[l]
dp[i] = max(dp[i], cur)
#--------如果不接当前的单
if 0 < i:
dp[i] = max(dp[i - 1], dp[i])
return dp[rn - 1]
java 解法, 执行用时: 87 ms, 内存消耗: 64.1 MB, 提交时间: 2023-09-17 11:59:22
class Solution {
public long maxTaxiEarnings(int n, int[][] rides) {
int len = rides.length;
Arrays.sort(rides, (a, b) -> (int)(a[1] - b[1]));
long[] dp = new long[len];
dp[0] = rides[0][2] + rides[0][1] - rides[0][0];
for (int i = 1; i < len; i++) {
dp[i] = Math.max(dp[i - 1], (long)(rides[i][2] + rides[i][1] - rides[i][0]));
int k = help(rides, 0, i - 1, rides[i][0]);
if (rides[k][1] <= rides[i][0]) dp[i] = Math.max(dp[i], dp[k] + rides[i][2] + rides[i][1] - rides[i][0]);
}
return dp[len - 1];
}
private int help(int[][] rides, int i, int j, int target) {
while (i < j) {
int mid = i + (j - i + 1) / 2;
if (rides[mid][1] <= target) {
i = mid;
} else {
j = mid - 1;
}
}
return i;
}
// 基于堆+dp
public long maxTaxiEarnings2(int n, int[][] rides) {
/*
堆+DP:与LC2054.两个最好的不重叠活动 比较类似
1.先按照上车时间升序排序rides数组
2.创建一个堆，这个堆的元素是[下车时间,当前下车时间为最后一趟的最大盈利]，按照a[0]升序排序
3.遍历rides数组，将堆中下车时间小于等于当前上车时间的元素弹出并记录最大值，将最大值+当前盈利作为新的一对并入堆
4.这样就可以动态地维护结束时间在某个上车时刻之前的最大盈利并以此计算出当前趟车为结尾的最大盈利，整个过程维护结果的最大值
*/
// 按照上车时间升序排序rides数组
Arrays.sort(rides, Comparator.comparingInt(a -> a[0]));
// [下车时间,当前下车时间为最后一趟的最大盈利]
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
long res = 0;
long max = 0;
for (int[] ride : rides) {
while (!pq.isEmpty() && pq.peek()[0] <= ride[0]) {
max = Math.max(max, pq.poll()[1]);
}
// 当前车结尾的最大盈利
long cur = max + ride[1] - ride[0] + ride[2];
// 维护结果并入堆
res = Math.max(res, cur);
pq.add(new long[]{ride[1], cur});
}
return res;
}
}
cpp 解法, 执行用时: 504 ms, 内存消耗: 137 MB, 提交时间: 2023-09-17 11:58:19
class Solution {
public:
long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
vector<long long> dp(n+1, 0); //dp[i]表示出租车从1行驶到i时的最大盈利
unordered_map<int, vector<pair<int, int>>> mp; //key为终点,val为vector,vector里的每个元素为(起点,小费)组成的pair
for(int i = 0; i < rides.size(); i++){
mp[rides[i][1]].push_back(make_pair(rides[i][0], rides[i][2]));
}
for(int i = 1; i <= n; i++){
dp[i] = dp[i-1]; //行驶到i的最大盈利必定大于等于行驶到i-1的盈利,当i不是乘客的终点时,dp[i]=dp[i-1]
if(mp.count(i) > 0){
for(auto p : mp[i]){ //mp[i]为vector,vector里的每个元素为(起点,小费)组成的pair
dp[i] = max(dp[i], dp[p.first] + i - p.first + p.second); //对每一个(key,val)组合计算最大盈利
}
}
}
return dp[n];
}
};
golang 解法, 执行用时: 224 ms, 内存消耗: 21.3 MB, 提交时间: 2023-09-17 11:57:41
/**
* 定义 f[i] 表示行驶到 i 时的最大盈利。考虑状态转移，一方面，我们可以不接终点为 i 的乘客，
* 这样有 f[i]=f[i−1]；另一方面，我们可以接所有终点为 i 的乘客中收益最大的，
* 这样有 f[i]=max(f[start]+i−start+tipp)，二者取最大值。
* 最终答案为 f[n]。
*/
func maxTaxiEarnings(n int, rides [][]int) int64 {
f := make([]int, n+1)
groups := make([][][2]int, n+1)
for _, r := range rides {
start, end, tip := r[0], r[1], r[2]
groups[end] = append(groups[end], [2]int{start, tip}) // 按终点位置分组
}
for end := 1; end <= n; end++ { // 从前往后枚举终点
f[end] = f[end-1]
for _, r := range groups[end] {
start, tip := r[0], r[1]
f[end] = max(f[end], f[start]+end-start+tip) // 接所有终点为 end 的乘客中收益最大的
}
}
return int64(f[n])
}
func max(a, b int) int { if b > a { return b }; return a }