1、前言

2、思路

这道题跟1235题一样，都是先按照结束时间排序（这里是结束地点），然后就是选第i个和不选第i个。不选第i个，就是前面dp[i-1]；选第i个，那得往前走到第一个结束时间<=第i个的开始时间

3、代码

class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        Arrays.sort(rides, (o1, o2) -> o1[1] - o2[1]);
        int m = rides.length;
        long[] dp = new long[m + 1];
        for(int i = 1; i <= m; i++){
            int j = i - 1;
            for(; j >= 0; j--){
                if(rides[j][1] <= rides[i - 1][0]){
                    break;
                }
            }
            dp[i] = Math.max(dp[i - 1], dp[j + 1] + rides[i - 1][1] - rides[i - 1][0] + rides[i - 1][2]);
        }
        return dp[m];
    }
}