2008. 出租车的最大盈利 --力扣 --JAVA

简介: 你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ,你想要从 1 开到 n ,通过接乘客订单盈利。你只能沿着编号递增的方向前进,不能改变方向。乘客信息用一个下标从 0 开始的二维数组 rides 表示,其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi ,愿意支付 tipi 元的小费。每一位 你选择接单的乘客 i ,你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。给你 n 和 rides ,请你返回在最优接单方案下,你能盈利 最

 题目

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

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

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

给你 nrides ,请你返回在最优接单方案下,你能盈利 最多 多少元。

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

解题思路

    1. 根据每段路程的终点进行统计记录;
    2. 记录每个位置能产生的最大收益,将数据归到终点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];
        }
    }

    网络异常,图片无法展示
    |


    目录
    相关文章
    |
    2月前
    |
    算法 Java
    [Java·算法·简单] LeetCode 9. 回文数 详细解读
    [Java·算法·简单] LeetCode 9. 回文数 详细解读
    22 0
    |
    2月前
    |
    Java
    383. 赎金信 --力扣 --JAVA
    给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能c里面的字符构成。 如果可以,返回 true ;否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。
    23 1
    |
    13天前
    |
    Java
    LeetCode题解-逆波兰表达式求值-Java
    逆波兰表达式求值-Java
    7 0
    |
    13天前
    |
    Java
    |
    13天前
    |
    Java
    |
    13天前
    |
    Java
    LeetCode题解-二叉搜索树中第K小的元素-Java
    LeetCode题解-二叉搜索树中第K小的元素-Java
    6 0
    |
    13天前
    |
    Java
    |
    13天前
    |
    Java
    LeetCode题解- 两两交换链表中的节点-Java
    两两交换链表中的节点-Java
    7 0
    |
    13天前
    |
    Java
    LeetCode题解-合并K个有序数组-Java
    合并K个有序数组-Java
    5 0
    |
    13天前
    |
    Java

    相关产品

  1. 云迁移中心