题目
你驾驶出租车行驶在一条有
n个地点的路上。这n个地点从近到远编号为1到n，你想要从1开到n，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。乘客信息用一个下标从 0 开始的二维数组
rides表示，其中rides[i] = [starti, endi, tipi]表示第i位乘客需要从地点starti前往endi，愿意支付tipi元的小费。每一位 你选择接单的乘客
i，你可以 盈利endi - starti + tipi元。你同时 最多 只能接一个订单。给你
n和rides，请你返回在最优接单方案下，你能盈利 最多 多少元。注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。
解题思路
- 根据每段路程的终点进行统计记录；
- 记录每个位置能产生的最大收益，将数据归到终点n；
代码展示
class Solution { public long maxTaxiEarnings(int n, int[][] rides) { Map<Integer,List<int[]>> groups = new HashMap<>(); for (int[] r : rides){ int start = r[0]; int end = r[1]; int tip = r[2]; List<int[]> group = groups.getOrDefault(end, new ArrayList<>()); group.add(new int[]{start, end - start + tip}); groups.put(end, group); } long[] profits = new long[n + 1]; profits[0] = 0; profits[1] = 0; //1的位置不会有人下车，所以从2开始计算 for (int i = 2; i <= n; i++){ profits[i] = profits[i - 1]; List<int[]> group = groups.get(i); if(group != null){ for (int[] p : group){ profits[i] = Math.max(profits[i],profits[p[0]] + p[1]); } } } return profits[n]; } }
网络异常，图片无法展示
|
